What is Time Complexity?
Time complexity is the measure of efficiency of an algorithm as the size of the input grows.
It tells us how many operations an algorithm takes to complete, depending on input size n.
💡 Myth: Time complexity ≠ Time taken
✅ Fact: Time taken depends on machine, language, and environment.
✅ Time complexity is theoretical—it gives a general idea of algorithm performance.
What is an Algorithm?
An algorithm is simply a step-by-step solution to a problem.
Key Insight:
Lower time complexity = Better performance
So we prefer algorithms with less complexity when solving problems.
🔍 Example: Linear Search vs Binary Search
Linear Search:
Works on both sorted and unsorted arrays
Time Complexity: O(n)
Example:
// array = [2, 3, 4, 5, 6]
// Find 4 by looping through each element
Binary Search:
Works only on sorted arrays
Time Complexity: O(log n)
Example:
// array = [2, 3, 4, 5, 6]
// Start with middle, divide in half repeatedly
Feature Linear Search Binary Search
Input Requirement Sorted/Unsorted Sorted only
Approach Loop through each Divide & conquer
Time Complexity O(n) O(log n)
✅ Binary Search is faster and more efficient than Linear Search on sorted data.
🧠 Common Time Complexities (With Examples):
O(1) — Constant Time
Example: arr5
O(log n) — Logarithmic Time
Example: Binary Search
O(n) — Linear Time
Example: Linear Search
O(n log n) — Linearithmic Time
Example:
for (i = 0; i < n; i++) {
binarySearch();
}
O(n²) — Quadratic Time
Example: Nested loops (e.g., bubble sort)
O(n³) — Cubic Time
Example: Three nested loops
O(2ⁿ) — Exponential Time
Example: Recursive Fibonacci
O(n!) — Factorial Time
Example: Generating all permutations
⚠️ Note: O(2ⁿ) and O(n!) are rarely used because they're very inefficient.
🔺 Time Complexity Graph:
Here’s a visual graph representing different complexities from best to worst:
Time Complexity Graph
Final Time Complexity Ranking:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Top comments (0)