We always hear below common terms in the world of computer science:

**Data Structure-**It defines how the data is arranged in computer’s memory. For example- arrays, stacks , linked lists are few of the popular data structures.

**Algorithm-**It is a set of instructions used to manipulate data structures. For example- sorting algorithm, searching algorithm etc.

**Time Complexity-**It is a measurement of rate of growth of time taken by any algorithm with respect to the increase in input size.

**Space Complexity-**Similar to the time complexity, it is a measurement of rate of growth of memory space taken by any algorithm with respect to the increase in input size.

**Asymptotic Notation-**It is a standard used for determining time/space complexities of an algorithm.

There are three basic asymptotic notations-

**1. Big O Notation [O]**

This notation represents tight upper bound of the given function.

Analytically we say as:

*f*(*n*) belongs to O(*g*(*n*)) as there exists*c*> 0 (e.g.,*c*= 1) and*n*0 (e.g.*n*0 = 5) such that*f*(*n*) ≤*c**g*(*n*) whenever*n*≥*n*0.
Lets see it through an example-

We have another function f(n) = 5n+4. Lets find the
tightest upper bound of this function. By tightest upper bound I mean we have
to find an another function (say g(n))
that will be always higher when we multiply g(n) by some constant (say
c) and add some value of n (say n0) to it.

By looking to f(n) we can say that if we have a
function g(n) = 6n then it will be the tightest upper bound of f(n). In other words:

*f*(n) ≤*c**g*(n) for c=6 & n0=4. To represent it in Big O we say f(n) = O(n) & it is read as*.***"f of n is big oh of g of n"**
Now you might say what if you have taken g(n) =
6n

^{2}or g(n) = 6n^{3 }?
Well, you are right! And in this case complexity will be O(n

^{2}) and O(n^{3}) respectively because f(n) will always be less than or equal to g(n) for any value of n.
But since we use Big O notation to represent

Big O notation is usually used to specify time/space complexity of the given algorithm in

__tightest upper bound__of the function, we will say f(n) = O(n) instead of O(n^{2}) or O(n^{3}).Big O notation is usually used to specify time/space complexity of the given algorithm in

**worst case**scenario. Worst case scenario is the situation when algorithm takes maximum time to run or maximum memory during it's execution.
## No comments:

## Post a Comment