DATASTRUCTURE AND ALGORITHM PART 2

Define Big ‘O’ notation. Compare linear logarithmic, linear and quadratic order function.

We can represent a linear algorithm (one where the number of steps increases in direct proportion to the amount of data) by the notation O(n), which read order of ‘n’. This notation means that for large value of n (where n is quantity that measures the amount of data being processed by the algorithm), the no. of steps taken by the algorithm is directly proportional to the amount of data being processed. So, all the algorithms can be classified by giving their order in the form of big ‘O’ notation. To do this, we must find an expression for the dependent of the number of steps in the algorithm on the amount of data being processed.

The most common order of algorithms is:

1.      Constant (O(1)): The number of steps is independent of the amount of data or it means that a constant number of steps is required, where constant can be any number not necessary just one.

Eg. An algorithm that always requires 15 steps is still an O(1) algorithm.

2. Linear (O(n)): algorithms like the average case of the sequential search.

3. Logarithmic (O(logn)): algorithm like binary search

4. Log-linear (O(nlogn)): algorithm where the leading term is proportional to the product of the amount of data n by the algorithm of the amount of data (logn). The most efficient sorting algorithms are of this type.

5. Quadratic (O(n^2)): algorithms where the number of steps depends on the square of the amount of work that must be done. Some sorting is of this type.

Consider a situation in which we can solve a problem in three ways: one is linear, another is linear logarithmic and third is quadratic. The magnitude of their efficiency for a problem containing 10000 elements shows that the linear solution requires a fraction of second while the quadratic solution requires upto 20 minutes.

Efficiency	Big O notation	Iterations	Estimated time
Logarithmic	O(logn)	14	microseconds
Linear	O(n)	10000	0.1 seconds
Linear log	O(nlogn)	140000	2 seconds
Quadratic	O(n^2)	10000^2	15-20 minutes
Polynomial	O(n^k)	10000^k	hours
Exponential	O(c^n)	2^10000	Intractable
Factorial	O(n!)	10000!	Intractable

This table contains an estimate of the time needed to solve the problem given different efficiencies.