Faangprep Logo
Log inStart free
Browse curriculum

Time Complexity

Time complexity measures how the number of operations grows as the input size (N) grows, not how many seconds an algorithm takes.

N UP TO 50

O(n²)

Operations at n = 1

O(1) 1
O(log n) 0
O(n) 1
O(n log n) 0
O(n²) 1

 

At n = 1 every complexity costs about the same. This is why small inputs tell you nothing about which algorithm to pick.

Next

n = 2: constant 1, log 1, linear 2, n log n 2, quadratic 4. Quadratic is now 2× linear.

Highlight

Intuition

Time complexity isn't about measuring how many seconds an algorithm takes. It's about measuring how the number of operations grows as the input size (N) grows.

Concept

  • O(1) Constant: Time doesn't change with N (e.g., accessing array index).
  • O(log n) Logarithmic: Time grows slowly (e.g., Binary Search).
  • O(n) Linear: Time grows directly with N (e.g., simple loop).
  • O(n log n): Common in efficient sorting (e.g., Merge Sort).
  • O(n²) Quadratic: Time grows rapidly (e.g., nested loops).

How it Works

Analyzing Code:

  • Count the loops.
  • Check if loops are nested.
  • See if the loop range depends on N.
  • Ignore constants (O(2n) becomes O(n)).

Step-by-Step Breakdown

Use the interactive chart:

  • Slider: Increase N to see how the curves diverge.
  • Toggle: Click buttons to isolate specific complexities.
  • Observe: Notice how O(n²) skyrockets compared to O(n).

When to Use

  • Always! Understanding complexity is key to writing efficient code.
  • When optimizing for large datasets.

When NOT to Use

  • For very small N, readability might be more important than optimization.

How to Identify

"Optimize performance", "Constraints: N ≤ 10^5", "Time Limit Exceeded".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Next

Space Complexity

Frequently Asked Questions

Does time complexity tell me how many seconds my code will take?

No. It describes how the number of operations grows as the input size N grows, not wall-clock time. Two O(n) algorithms can differ by a large constant factor, and that constant is exactly what Big-O drops.

Why do we drop constants and lower-order terms?

Because complexity describes behaviour as N gets large. At N = 1,000,000 the n² term in n² + n dwarfs the n, so the sum is reported as O(n²), and O(2n) is reported as O(n).

How do I read the complexity off a loop?

Count the nesting. One loop over N is O(n), two nested loops over N are O(n²), and a loop whose counter doubles or halves each step is O(log n). A loop whose range does not depend on N contributes O(1).