Asymptotic Analysis and notation

Index

1. Time Complexity
2. Common DS Operations Time Complexity and Space Complexity

---

Time-complexity

Big-O notation: 𝑂O

It describes the asymptotic upper bound, the worst case of time complexity. i.e the max number of times a statement executes. 

Measurement of time complexity

1. O(N) Linear TC – When the number of operation growth is proportional to input i.e same number of operation as the input size then it’s Linear TC
2. O(N^2) – Quadratic Algorithm TC
3. O(LogN) -when algorithm decreases the input data in each step
   • Example Binary search
4. O(2^n) – opeation doubles with each increment in input data.

Growth Order

O(n!) > O(2 ^n) > O(n^3) > O(n^2) > O(nlogn) > O(n) > O(Log N) > O(sqrt(N)) > 1

---