Time Complexity Basics

Time complexity is a way to describe how the running time of an algorithm or operation grows as the input size n increases.

Instead of focusing on exact milliseconds, we use Big‑O notation to reason about growth rates and compare options at a high level.

Common Complexity Classes

Some typical time complexities:

  • O(1) – constant time.
  • O(log n) – logarithmic.
  • O(n) – linear.
  • O(n log n) – linearithmic.
  • O(n²) – quadratic.

In practice:

  • O(1) and O(log n) are usually “fast enough” for large n.
  • O(n log n) is common for sorting and many divide‑and‑conquer algorithms.
  • O(n²) is often too slow when n is in the tens or hundreds of thousands.

Amortized Complexity

Some operations are cheap most of the time but occasionally expensive. We use amortized analysis to capture average cost over a sequence of operations.

Examples:

  • Dynamic array (vector / ArrayList) push at end:
    • Most pushes are O(1).
    • Occasionally, the array is resized and elements are copied (more expensive).
    • Amortized cost per push is still O(1).
  • Hash table operations:
    • Expected insert/lookup/delete are O(1) over many operations, with occasional O(n) rehashing.

In interviews, if a data structure guarantees good amortized behavior, you can often treat it as effectively O(1) per operation unless the problem is about worst‑case guarantees.

Data Structures and Time Complexity

Different data structures offer different trade‑offs:

  • Arrays:
    • Index access: O(1).
    • Insert/delete in middle: O(n).
  • Linked lists:
    • Insert/delete at known node: O(1).
    • Search by value / index: O(n).
  • Hash tables:
    • Expected insert/lookup/delete: O(1) average.
    • Worst‑case: O(n) if many collisions.
  • Balanced BSTs:
    • Search/insert/delete: O(log n).
  • Heaps:
    • Insert / extract top: O(log n).
    • Peek top: O(1).

Understanding these costs lets you choose the right structure for your performance needs.

Big-O in Interviews

Interviewers typically expect you to:

  • State the time complexity of your main operations.
  • Explain why a particular structure is suitable (O(1) vs O(log n) vs O(n)).
  • Compare alternatives:
    • “Array is fine here because we rarely insert in the middle.”
    • “We need a hash map because we require many membership checks.”

You don’t need to be overly formal, but you should be precise about how your choices scale with n.