Big O basics

Additional TopicsEntryalgorithms

The Question

What is Big O notation and what are the common complexities?

What a Strong Answer Covers

• At least 5 complexities with examples. "Drop constants." Space vs time distinction.

Senior-Level Answer

Big O notation is a mathematical notation used in computer science to describe the upper bound of an algorithm's growth rate as input size n approaches infinity. It answers the question: how does the time (or space) this algorithm needs scale as the input grows? By convention, Big O focuses on the dominant term and drops constants and lower-order terms -- O(2n + 5) is written O(n) because for large n the linear term dominates.

Big O describes worst-case complexity by default (unless stated otherwise). Omega notation describes best case; Theta notation describes tight bounds (both upper and lower). In interviews, Big O and worst case are almost always what is meant.

The common complexity classes, from best to worst: O(1) -- constant time; the operation takes the same time regardless of input size. Hash table lookups, array index access. O(log n) -- logarithmic; input is halved each step. Binary search, balanced BST operations. O(n) -- linear; every element is touched once. Single-pass array scan, linked list traversal. O(n log n) -- linearithmic; appears in efficient comparison sorts. Merge sort, heap sort, Timsort. O(n^2) -- quadratic; nested loops over the input. Bubble sort, insertion sort on unsorted data. O(2^n) -- exponential; every additional element doubles the work. Recursive Fibonacci without memoization, subset enumeration. O(n!) -- factorial; permutation generation, brute-force traveling salesman.

Space complexity follows the same notation and describes auxiliary memory usage -- the extra memory beyond the input. A recursive algorithm that makes n levels of recursive calls uses O(n) stack space even if it uses no other memory.

Common analysis traps: Big O is asymptotic -- O(n^2) can be faster than O(n log n) for very small n due to constants. Amortized analysis is relevant for operations like dynamic array append, which is O(1) amortized even though occasional resizes are O(n). Average case often differs from worst case -- hash table lookup is O(1) average but O(n) worst case with many collisions.

In interviews, always state both time and space complexity for any algorithm you write.

What Separates a 2/3 from a 3/3

Common Mistakes

• Keeping constants in Big O -- O(2n) should be simplified to O(n)
• Forgetting space complexity -- only reporting time complexity when both are asked for
• Thinking Big O is always worst case -- it is an upper bound, and explicitly noting average vs worst case matters
• Claiming all O(n log n) algorithms beat O(n^2) regardless of input size -- for very small n, constants matter more

Follow-Up Questions

• What is amortized time complexity? — Amortized analysis averages cost over a sequence of operations -- a dynamic array append is O(1) amortized because expensive O(n) resizes are rare relative to total operations.
• What is the time complexity of inserting into a sorted array? — O(n) -- finding the position is O(log n) with binary search, but shifting elements to make room is O(n).
• Can two algorithms with the same Big O have very different real-world performance? — Yes -- constant factors, cache behavior, and branch prediction all matter. A cache-friendly O(n^2) algorithm can beat O(n log n) for small n.
• What is the space complexity of a recursive DFS on a graph with n nodes? — O(n) in the worst case for the call stack depth -- on a path graph, the recursion depth equals n.

Related Questions

• CAP theorem
• SQL vs NoSQL
• N+1 problem
• AI tools in workflow
• Redis Internals