🔹 Introduction
When we write a program, it is not enough that it works correctly — it should also be efficient. This is where Time Complexity becomes important.
Time complexity helps us understand how fast an algorithm runs as the input size increases. It is one of the most frequently asked topics in exams like UGC NET and in coding interviews.
🔹 What is Time Complexity?
Time Complexity is a measure of how the execution time of an algorithm grows with the size of input.
Instead of calculating exact time in seconds, we represent it using mathematical expressions.
👉 It is commonly expressed using Big O Notation.
🔹 What is Big O Notation?
Big O Notation describes the upper bound of an algorithm’s running time.
It focuses on:
- Worst-case scenario
- Growth rate of execution time
Example:
- O(1) → Constant time
- O(n) → Linear time
- O(n²) → Quadratic time
🔹 Common Time Complexities Explained
1. O(1) – Constant Time
Execution time does not change with input size
Example:
int x = arr[0];
2. O(n) – Linear Time
Time increases linearly with input size
Example:
for(int i=0; i<n; i++) {
printf("%d", i);
}
3. O(n²) – Quadratic Time
Used in nested loops
Example:
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
printf("%d", i*j);
}
}
4. O(log n) – Logarithmic Time
Very efficient, used in binary search
🔹 Why Time Complexity Matters
- Helps compare algorithms
- Improves performance
- Reduces execution time
- Important for large datasets
🔹 Real-Life Example
Searching a name in a phonebook:
- Linear search → O(n)
- Binary search → O(log n)
👉 Clearly, binary search is faster.
🔹 Common Mistakes
- Ignoring worst-case analysis
- Focusing on constants (which are ignored in Big O)
- Not understanding nested loops
🔹 Conclusion
Time complexity is a fundamental concept that helps developers choose efficient algorithms. Understanding Big O notation allows you to analyze and optimize your code effectively.
If you are preparing for competitive exams or interviews, mastering time complexity is essential.