Page 26 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 2: Data Structure Operations and Algorithms Complexity

Self Assessment Notes

Fill in the blanks:
3. An ............................. is a clearly specified set of simple instructions to be followed to solve
a problem.

4. In order to analyze algorithms in a formal framework, we need a .................... of computation.
5. The............................. of an algorithm is a function describing the efficiency of the algorithm
in terms of the amount of data the algorithm must process.

6. ............................. is a function describing the amount of time an algorithm takes in terms of
the amount of input to the algorithm.
7. ............................. is a function describing the amount of memory (space) an algorithm
takes in terms of the amount of input to the algorithm.

2.3 Big O Notation

When solving a computer science problem there will usually be more than just one solution.
These solutions will often be in the form of different algorithms, and you will generally want to
compare the algorithms to see which one is more efficient. This is where Big O analysis helps –
it gives us some basis for measuring the efficiency of an algorithm

“Big O” refers to a way of rating the efficiency of an algorithm. It is only a rough estimate of the
actual running time of the algorithm, but it will give you an idea of the performance relative to
the size of the input data.
The motivation behind Big-O notation is that we need some way to measure the efficiency of
programs but there are so many differences between computers that we can’t use real time to
measure program efficiency. Therefore we use a more abstract concept to measure algorithm
efficiency.
An algorithm is said to be of order O(expression), or simply of order expression (where expression
2
is some function of n, like n and n is the size of the data) if there exist numbers p, q and r so that
the running time always lies below between p.expression+q for n > r. Generally expression is
made as simple and as small as possible.
Definition: Let f(n) and g(n) be functions, where n is a positive integer. We write f(n) = O(g(n)) if
and only if there exists a real number c and positive integer n0 satisfying 0 <= f(n) <= cg(n) for all
n >= n0.
We say, “f of n is big oh of g of n.” We might also say or write f(n) is in O(g(n)), because we can
think of O as a set of functions all with the same property. But we won’t often do that in Data
Structures.
This means that, for example, that functions like n + n, 4n – n log n + 12, n /5 – 100n, n log n, 50n,
2
2
2
2
and so forth are all O(n ).
Every function f(n) bounded above by some constant multiple g(n) for all values of n greater
than a certain value is O(g(n)).
Example:

2
2
Show 3n + 4n – 2 = O(n ).

LOVELY PROFESSIONAL UNIVERSITY 19