Time complexity = how fast runtime grows when input size grows
Rules:
- We ignore the constants.
- Consider the worst case not the best case while caculation
- Add when sequential, multiply when nested
Major time complexities:-
- Constant - O(1) - very fast to execute and this is the best ever possible
- Logarithmic - O(log n) - very fast after constant
- Linear - O(n)
- Linearithmic - O(n log n)
- Polynomial - O(n ^ 2),O(n ^ 3)
- Exponential - O(2^n)
- Factorial - O(n!)
O(1) - constant time complexity
It is constant time complexity means no looping no recurssions just one condition or few condition to get the solution of the problem.
O(log n) Maths:-
As mentioned about log n, How many time does n is divisble by 2 to reach 1. Means we are processing only log n elments eg:- binary search (each time we will make input size into half means /2) - That means how many time we are making half is the time complexity.
O(n) - Linear time complexity - Like loop through the n elements.
O(Log n) < O(n) as O(n) is processing n elements and O(log n) is processing just log n elements.
O(n log n):-
Consider it like we are doing log n operations n times. eg:- check n elements in a array using binary search as we discussed binary is O(log n) but we are doing it for n times. here we are not doing sequentially we are doing with nested so we multiply n * log n
O(n 2 ) - Polynomial:-
As rule stated when nested we multiply. O(n) nested with O(n). Like one for loop inside another for loop is like nested for loop. Which is slower as input grows. Mostly we try to reduce polynomial to other time complexities.
O(2 n) - Exponential:-
It is like work double every time input size increase by 1. Like combinations if you know the maths. (I dont know).
eg:- Consider a recursion , each call of one input make 2 more calls (f(n) = f(n-1) + f(n-1))
—Need to check more about it.
O(n!) - Factorial
Worst time complexity that takes lots of time to run. This happens when we trying all permutations
eg: Imagine we need to make stand n people stand n = 5 → 120 ways n = 10 → 3628800 ways
like person can stand in n ways after 2 nd person can stand in n-1 ways soo on n * n-1 * n-2 * … = n!
Travelling salesman problem :- (where no optimization is present):- Problem:- Salesman need to visit all cities he has, To calculate the cities order he need to visit we need to calculate all the distances from one city to another like city1 → city 2 → city 3 and also city2→ city3
We need to do all the permutation and decide one order.
Conclusion - First we need to try doing brute and try to reduce input size so that we can reduce the time complexity drastically.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)