Page 2 - Lesson Note-Algorithmic Efficiency

O(N)
O(N) describes an algorithm whose performance will grow linearly and in direct proportion
to the size of the input data set. (Ex. Linear search)

2
O(N )
2
O(N ) represents an algorithm whose performance is directly proportional to the square of
the size of the input data set. (Ex. Algorithms with nested iterations).

N
O(2 )
N
O(2 ) denotes an algorithm whose growth doubles with each addition to the input data set.
N
The growth curve of an O(2 ) function is exponential - starting off very shallow, then rising
meteorically. (Ex. Recursive calculation of Fibonacci series)

Estimation of algorithm efficiency is performed to determine their growth function i.e. how
the algorithm will perform with the growth in its input size. Algorithmic efficiency only tells
its growth function and not its actual execution time.
Programs with smaller O value runs faster than bigger O value.

Program efficiency is defined in terms of its space and time complexity.
➢ One way to measure execution time of a function is track the actual time required by
a program to compute its result. Less the wall clock time better is the efficiency.
➢ Other way to calculate the number of steps required to compute the result. Less
number of steps (after expanding all loops) better is the efficiency.

Five cases to judge for finding out the time complexity of a piece of code are (with an
assumption, all steps take same time for execution):
1. Loops
2. Nested loops
3. Consecutive statements
4. If-then-else statements
5. Logarithmic complexity