Common Time Complexities Explained
Table of Contents
Common Time Complexities Explained
Let's understand the most common time complexities with simple Java examples and real-life analogies.
1. O(1) – Constant Time
An algorithm runs in constant time if the number of operations remains the same regardless of the input size.
Real-Life Example
Finding the first page of a book.
Whether the book has 100 pages or 10,000 pages, opening the first page always takes one step.
Java Example
int[] numbers = {10, 20, 30, 40, 50};
System.out.println(numbers[0]);
Complexity
- Time Complexity: O(1)
- Space Complexity: O(1)
Array indexing is one of the best examples of O(1).
2. O(log n) – Logarithmic Time
The problem size is reduced by half after every step.
Real-Life Example
Searching a word in a dictionary.
You don't read every page. Instead, you repeatedly open near the middle.
Java Example
int low = 0;
int high = arr.length - 1;
while(low <= high){
int mid = (low + high) / 2;
if(arr[mid] == target)
return mid;
if(arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
Binary Search runs in O(log n).
3. O(n) – Linear Time
The running time grows directly with the input size.
Real-Life Example
Finding a student in an unsorted attendance register.
Java Example
for(int i = 0; i < arr.length; i++){
if(arr[i] == target)
return i;
}
This is called Linear Search.
Complexity
- Best Case: O(1)
- Average Case: O(n)
- Worst Case: O(n)
4. O(n log n)
This complexity is common in efficient sorting algorithms.
Examples
- Merge Sort
- Heap Sort
- Quick Sort (Average Case)
Why?
The array is repeatedly divided into smaller parts and then merged.
Number of levels = log n
Work at each level = n
Total work = n × log n
5. O(n²) – Quadratic Time
The algorithm compares every element with every other element.
Real-Life Example
Suppose every student in a classroom shakes hands with every other student.
The number of handshakes increases rapidly as more students join.
Java Example
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.println(i + " " + j);
}
}
This performs approximately n × n operations.
Examples
- Bubble Sort
- Selection Sort
- Insertion Sort (Worst Case)
6. O(2ⁿ) – Exponential Time
Each recursive call creates two more recursive calls.
Java Example
int fibonacci(int n){
if(n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
This recursive solution repeatedly solves the same subproblems.
Dynamic Programming improves this to O(n).
7. O(n!) – Factorial Time
This is one of the slowest complexities.
Algorithms generate every possible arrangement of data.
Examples
- Travelling Salesman (Brute Force)
- Generating all permutations
Even for small values of n, execution becomes extremely slow.
Best, Average and Worst Case Complexity
| Case | Description |
|---|---|
| Best Case | Minimum running time |
| Average Case | Expected running time |
| Worst Case | Maximum running time |
Example: Linear Search
| Situation | Complexity |
|---|---|
| Element found first | O(1) |
| Element found middle | O(n) |
| Element found last | O(n) |
| Element not found | O(n) |
Interviewers usually ask for the worst-case time complexity unless they specify otherwise.
Quick Revision Table
| Complexity | Meaning | Example |
|---|---|---|
| O(1) | Constant | Array Access |
| O(log n) | Divide by Half | Binary Search |
| O(n) | Linear | Linear Search |
| O(n log n) | Efficient Sorting | Merge Sort |
| O(n²) | Nested Loops | Bubble Sort |
| O(2ⁿ) | Recursive Explosion | Naive Fibonacci |
| O(n!) | Permutations | Brute Force TSP |
➡️ Next: In Part 3, we'll learn Space Complexity, Big Ω (Omega), Big Θ (Theta), solve interview questions, cover common mistakes, and finish the article with FAQs and navigation to the next lesson.
Comments
Post a Comment