DSA · Chapter 2 of 40
Time Complexity
Time complexity describes how the running time of an algorithm grows as the input size n grows. We express it with Big-O notation, which ignores constants and keeps only the dominant term.
O(1) means constant time, O(log n) grows very slowly, O(n) grows in proportion to the input, O(n log n) is typical of good sorting, and O(n^2) becomes slow quickly.
How to count
Count how many times the innermost work happens. One loop over n items is O(n); a loop inside a loop is O(n^2); halving the input each step is O(log n).
Best, average, worst
Interviewers usually mean worst case. Linear search is O(1) if the item is first, but O(n) in the worst case.
Example 1 (python)
# O(n) - one pass
def total(nums):
s = 0
for n in nums:
s += n
return s
print(total([1, 2, 3, 4]))Output
10Work grows linearly with the number of items.
Example 2 (python)
# O(n^2) - nested loops
pairs = 0
for i in range(4):
for j in range(4):
pairs += 1
print(pairs)Output
16For n = 4 the body runs 16 times; doubling n makes it 4x slower.
Key points
- Big-O keeps only the dominant term and drops constants.
- O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n).
- Nested loops over the same input usually mean O(n^2).
- Interviews normally ask for worst-case complexity.
💡 Note: If you can turn an O(n^2) solution into O(n) with a hash map, that is usually the expected answer.