Time Complexity
Definition:
Time complexity is the rate at which the running time of an algorithm increases with the
size of input (n).
It does not depend on actual time (in seconds) because execution time differs from one
system to another.
Key Idea
Time Complexity ≠ Time Taken
It shows how fast runtime grows as input increases.
Measured Using: Big-O Notation
We represent time complexity as:
O(f(n))
where f(n) shows how runtime grows as input n increases.
Example
for(int i = 1; i <= n; i++) {
cout << "Hello";
}
Loop runs n times
Each iteration takes constant time
Time complexity = O(n)
Three Rules to Remember
1. Always consider worst case
o ⇒ Analyze in O(worst case).
o Example: Searching in an array — element found at the last index.
2. Avoid constants
o O(3n) → becomes O(n)
o Constant factors don’t matter for large n.
3. Avoid lower order terms
o O(n² + n + 1) → becomes O(n²)
Types of Cases
Case Meaning Example Input Time Complexity
Best Case Minimum steps element found early O(1)
Average Case Typical scenario random input O(n/2)
Worst Case Maximum steps element found last O(n)
Always compute for worst case in coding interviews.
Examples
[Link] Loop
for(int i=0; i<n; i++)
cout << i;
✅ O(n)
[Link] Loops
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cout << i << j;
✅ O(n²)
[Link] Loop Depends on i
for(int i=0; i<n; i++)
for(int j=0; j<i; j++)
cout << i << j;
= 1 + 2 + 3 + … + n → O(n²)
Common Big-O Complexities
Big-O vs Θ vs Ω
Notation Meaning Used for
O(f(n)) Upper bound Worst case
Θ(f(n)) Tight bound Average case
Ω(f(n)) Lower bound Best case
Space Complexity
It’s the memory required by the program during execution, including:
Input storage
Variables
Recursion stack
Data structures