What is Big O notation?
Big O notation describes how the running time or memory of an algorithm grows as the input gets larger. It focuses on the worst case and ignores constants, so it captures the overall trend rather than exact timings. For example O(n) means the work grows in line with the input size, and O(1) means the work stays constant no matter the size.
Why we use it
Two algorithms can both solve a problem, but one may be far slower on large inputs. Big O gives us a simple language to compare them without depending on the machine or the programming language.
Common complexities from fast to slow
- O(1): constant time, such as reading an array element by index.
- O(log n): logarithmic, such as binary search.
- O(n): linear, such as scanning a list once.
- O(n log n): common for good sorting algorithms.
- O(n squared): nested loops over the same data.
- O(2 to the n): exponential, very slow, seen in brute force recursion.
# O(n): one loop over n items
for x in items:
print(x)
# O(n squared): a loop inside a loop
for a in items:
for b in items:
print(a, b)Always state the time and the space complexity when you finish a solution, even if the interviewer does not ask. Saying this runs in O(n) time and O(1) extra space shows maturity and often earns extra credit.
Common follow up questions
Related interview questions
Want the full DSA guide?
Read every DSA concept with notes, diagrams, and code in one place. Track your progress as you go.
Open the DSA guide All DSA questions