1 min read
The computation time taken by a piece of code or an algorithm.
Three types of Asymptotic Notations to express time complexity:
- Big-O Notation: Upper Bound
- Theta Notation: In between upper and lower bound
- Omega Notation: Lower Bound
But generally we used the Big-O Notation to express the time complexity in programming world.
Types of Time Complexity:
- Constant Time Complexity: O(1)
- Linear Time Complexity: O(n)
- Logarithmic Time Complexity: O(log n)
- Quadratic Time Complexity: O(n²)
- Exponential Time Complexity: O(2^n)
So, to calculate time complexity, you should count the number of operations in a program. And, No of operations that can be performed in one second by a machine = 10^7
● Array size = 4*10^7 -> This means you can iterate the array only once. O(N)
solution is needed.
● Array size = 10^3. O(N^2) at max.
● Array size = 10^5. O(N) or O(N log N)
● Array size = 10 O(2^N)
● Matrix N = 1000, M = 1000. Complexity O(N*M).
This is how you can look at the constraint and tell what time complexity will be needed.
So this is it for this article. I hope it helped you somewhere. Don't forget to support us and share with other geekians.Thank you, Have a nice day !!