Big O Notation

We are going to discuss run time characteristics of programs that we write day to day basis.

This picture is taken from bigocheatsheet.com which describes following things:

1. O(log n) , O(1) is described under excellent run time complexity of given program.
2. O(n) is described as fair runtime complexity of given program.This is also called liner algorithms.
3. O(n logn) is categorised as bad run time algorithms.
4. O(n^2) , O(2^n) and O(n!) are described as horrible run time complexity of the given code.

 We are going to  compare run time complexity time and use case for each constant time.

Constant time :- Algorithm takes same amount of time  regardless of size of input data. This is usually seen in Arrays (read operations).

Logarithmic :-  Algorithm takes O(log n) amount of time regardless of doubling the size of the input data or doubling the elements in the array structure. This kind of example seen in Search algorithms (binary search).

Linear :- Algorithm takes O(n) amount of time while adding elements to the collections of data such as linked list, arrays etc.

Quasilinear :- Algorithm takes O(n log n) of time because of lots of elements comparisons (sorting algorithms) 

Quadratic :- Algorithm takes O(n2) of time to complete. More input to the algorithm going to slow down the algorithm. This is usually seen in nested loop programs.

Exponential :-  Algorithm takes O(2n) of time to complete. Example is recursion programs.