Analysis of algorithms

Analysis involves measuring the performance of an algorithm. Performance is measured in terms of the following parameters: Space complexity and Time complexity

I. Space complexity — The amount of memory needed to perform the task. the space requirement of an algorithm, can be performed at two different times:

1. Compile time: Compile time space complexity is defined as the storage requirement of a program at compile time.

2. Run time: If the program is recursive or uses dynamic variables or dynamic data structures, then there is a need to determine space complexity at run-time. Memory requirement is the summation of the program space, data space, and stack space.

II. Time complexity — The amount of time taken by an algorithm to perform the intended task. Time complexity T (P) is the time taken by a program P, is the sum of its compile and execution times. It is system dependent.

Another way to compute it is to count the number of algorithm steps.

Best, Worst, and Average Cases

The best case complexity of an algorithm is the function defined by the minimum number of steps taken on any instance of size n.

The worst case complexity of an algorithm is the function defined by the maximum number of steps taken on any instance of size n.

The average case complexity of an algorithm is the function defined by an average number of steps taken on any instance of size n.

Big-O Notation

It is a theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items.

Big-O notation represents the upper bound of the running time of an algorithm. It gives the worst-case complexity of an algorithm.

The big-O notation can be derived from f (n) using the following steps:

1. In each term, set the coefficient of the term to 1.

2. Keep the largest term in the function and discard the others. The terms are ranked from the lowest to the highest as follows:

log2n … n … n log2n … n2 … n3 … nk … 2n … n!

Example:

Calculate the big-O notation for

Remove all coefficients. This gives n² + n  which, after removing the smaller factors, gives us n² which, in big-O notation, is stated as  O(f(n)) = O(n²).