Runtime grows linearly with input size

🎓 Prepared by students from Boğaziçi University

What is Big-O Notation?

Big-O notation describes how an algorithm's running time or memory use grows as the input size n grows, ignoring constants and lower-order terms. It lets programmers compare algorithms' worst-case efficiency at a glance.

Short answer

Big-O notation, written O(f(n)), gives the upper bound on how an algorithm's cost scales with input size n. Common classes include O(1), O(log n), O(n), O(n log n) and O(n²), from fastest to slowest growth.

Growth rates: O(1) vs O(log n) vs O(n) vs O(n²)

x: input size n · y: operationsO(1)O(log n)O(n)O(n²)

Try it: interactive calculator

Operations for O(n²) algorithm

100steps

= 10^2

Input size n10 elements

Step-by-step worked examples

A loop runs once for every element in a list of 8 items. What's its Big-O?

1 pass, 8 comparisons, 1 operation per element
T(n) = n → O(n)
For n = 8, roughly 8 operations

Binary search on a sorted list of 1,024 items — how many steps at worst?

Each step halves the search space: 1024 → 512 → 256 → ... → 1
Number of halvings = log₂(1024) = 10
O(log n) → about 10 comparisons, not 1024

Nested loops, both running n times over a list of n = 6 items — how many operations?

Outer loop: 6 iterations
Inner loop: 6 iterations each time
Total = 6 × 6 = 36 operations
T(n) = n² → O(n²)

Flashcards

Quick quiz

Q1.What does O(n) mean?

Correct answer: B. O(n) means the number of operations scales directly and proportionally with n.

Q2.Binary search on a sorted array has what time complexity?

Correct answer: C. Binary search halves the search space each step, giving logarithmic growth.

Q3.Which grows fastest as n increases?

Correct answer: C. O(n²) grows quadratically, outpacing linear and logarithmic growth for large n.

Q4.Why is Big-O usually about the worst case?

Correct answer: B. Worst-case analysis guarantees the algorithm won't perform worse than that bound, which is the safest planning assumption.

📄Download this topic as a printable worksheet (PDF)Summary + 10 questions + answer key — print it, share it in class.↓

Study better with Bounlu apps

Notek

The full card deck, worked steps and AI-tutor support for “What is Big-O Notation?” are in Notek — study by hand before your exam.

Get it free

PromyNever miss an exam or homework deadline with Promy: AI turns the dates in your inbox into reminders automatically.

Common mistakes

✗

Thinking Big-O measures exact running time in seconds. — Correct: Big-O measures how operations scale with input size, not actual clock time (which depends on hardware).

✗

Believing O(2n) and O(n) are meaningfully different. — Correct: Constants are dropped in Big-O — both simplify to O(n) since growth trend is what matters.

✗

Assuming O(n²) is always worse than O(n) for every input. — Correct: For small n an O(n²) algorithm can be faster in practice; Big-O only describes trends as n grows large.

✗

Confusing Big-O (upper bound/worst case) with average-case complexity. — Correct: Big-O caps the worst case; some algorithms (like quicksort) have worse worst-case than average-case complexity.

FAQ

What is Big-O notation?

Big-O notation, O(f(n)), describes the upper bound on how an algorithm's running time or memory grows as input size n increases.

What is the formula for Big-O?

There's no single formula — instead, you express the dominant growth term, e.g., T(n) = 3n + 5 simplifies to O(n).

What are examples of Big-O notation?

O(1) constant (array lookup), O(log n) logarithmic (binary search), O(n) linear (single loop), and O(n²) quadratic (nested loops/bubble sort).

How do you calculate Big-O for an algorithm?

Count how operations scale with n, keep only the fastest-growing term, and drop constants — e.g., 2n² + 3n becomes O(n²).