What is Time Complexity?
Time Complexity tells us how the running time of an algorithm grows when the input size n increases.
It is commonly represented using Big O Notation.
Asymptotic Notations
| Notation | Meaning |
|---|---|
| Ω (Omega) | Lower Bound / Best Case |
| Θ (Theta) | Tight Bound / Average Case |
| O (Big O) | Upper Bound / Worst Case |
Linear Search
| Case | Complexity |
|---|---|
| Best | O(1) |
| Average | O(n) |
| Worst | O(n) |
Common Time Complexities
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array access |
| O(log n) | Logarithmic | Binary Search |
| O(n) | Linear | Array traversal |
| O(n log n) | Linearithmic | Merge Sort, Heap Sort |
| O(n²) | Quadratic | Nested loops |
| O(2ⁿ) | Exponential | Recursive brute force |
| O(n!) | Factorial | Permutations |
1. O(1) – Constant Time
Direct access takes O(1).
2. O(n) – Linear Time
Loop runs n times → O(n).
3. O(log n) – Logarithmic
Why O(log n)?
At each comparison, half of the tree is eliminated.
Example: Binary SearchTime Complexity: O(log n)The search space is repeatedly divided in half.
4. O(n log n) – Linearithmic
Examples:
Merge Sort
Heap Sort
Quick Sort (Average)Time Complexity: O(n log n)
5. O(n²) – Quadratic
n × n = n²Time Complexity: O(n²)
For n = 3 → 3 x 3 = 9 operations.
Rules for Calculating TC
| Rule | Example | Result |
|---|---|---|
| Ignore constants | O(5n) | O(n) |
| Ignore lower terms | O(n + 100) | O(n) |
| Sequential loops | O(n) + O(n) | O(n) |
| Different sequential loops | O(n) + O(m) | O(n+m) |
| Nested loops | O(n) × O(n) | O(n²) |
| Different nested loops | O(n) × O(m) | O(nm) |
Sequential Loops
Nested Loops
O(n) × O(n) = O(n²)Complexity Order
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)Lower complexity = generally better performance for large inputs.