Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Algorithm Efficiency

Algorithm efficiency, captured by Big-O notation, describes how an algorithm's cost grows with input size n — written O(n), O(n2), O(log⁡n), and so on.


Quick Answer

Algorithm efficiency, captured by Big-O notation, describes how an algorithm's cost grows with input size n — written O(n), O(n2), O(log⁡n), and so on. Use it to compare methods before you run them on big data: for a million items, an O(n) scan takes about a million steps, an O(n2) comparison of every pair about a trillion, and an O(log⁡n) binary search about 20. Big-O keeps only the fastest-growing term and drops constant factors, so it predicts how the cost scales, not the exact time.

Why This Matters

Suppose a method takes 1 second on 1,000 items. On 1,000,000 items it takes about 2 seconds if it is O(log⁡n), about 17 minutes if it is O(n), and about 11.6 days if it is O(n2). A test run on small data cannot tell these apart, but the shape of the code can. Without that analysis, programs pass every small test and then freeze on real data.

Intuitive Explanation

Count steps instead of seconds. To find the largest of n numbers you look at each one once: about n steps. Double the list and you double the work; that is O(n), linear. To check whether any two students in a class share a birthday by comparing every pair, a class of n needs n(n−1)/2 comparisons: 435 for 30 students, 1,770 for 60. Doubling n roughly quadruples the work. That is O(n2), quadratic, and it usually comes from a loop inside a loop.

Some methods barely notice growth. Binary search on a sorted list throws away half the remaining items with each comparison, so 1,000 items need about 10 steps and 1,000,000 need about 20. Doubling n adds a single step: O(log⁡n). Between these sits O(nlog⁡n), the cost of good sorting methods like merge sort, and far above them all is O(2n), where each extra item doubles the work.

Big-O deliberately ignores details. 3n+50 steps and n steps are both O(n), because for large n the constants do not change how the cost scales. That is also its limit. A run that took 0.2 seconds on your laptop is a measurement of one input on one machine, not an efficiency class. On small inputs an O(n2) method with little overhead can beat an O(nlog⁡n) one; Big-O tells you which method wins once the data gets large.

Think of it like this. Big-O compares ways of running a party. Handing each guest an invitation takes time in proportion to the guest list: O(n). Having every guest shake hands with every other guest grows with the square: O(n2). Big-O asks how the job grows as the party gets bigger, not how fast one particular helper walks.

Core idea. Algorithm efficiency matters increasingly as data grows—a slow algorithm on small data may fail completely on large data.


When to Use

Use Big-O when a question asks how the cost scales: what happens if the input doubles, which method is better for large n, or how many steps a loop structure takes. Count loops: one pass over the data is O(n), a loop inside a loop over the same data is O(n2), halving the range each step is O(log⁡n). If the question asks for the exact step count on one specific input, just count or trace. If it asks what the steps are, you are describing the Algorithm itself.

Tip. Ask: Is the question how the number of steps grows as the input gets bigger, rather than the exact time?

How to Recognize It

Before reaching for Big-O, check that the input has a size that can grow and that you are comparing how work scales, not timing one run.

  1. Is there an input size n, such as the length of a list, that could get much larger?

    Yes means growth can be analysed. If the input is fixed, say always 10 items, Big-O tells you little and a direct count is better.

  2. Are you comparing how two methods behave as n doubles or grows a thousandfold?

    Yes is an efficiency question. If the question is whether a method gives the right answer at all, that is about the Algorithm itself.

  3. Does the code have a loop inside a loop, or halve the data at each step?

    Nested loops over n suggest O(n2); halving suggests O(log⁡n). Either way, the answer you want is a growth class.

  4. Is the plan to speed things up by adding processors rather than by changing the method?

    Yes points to Parallel Computing. More processors cut the time by a constant factor at best, while a better algorithm changes the growth rate.

Algorithm Efficiency vs Algorithm vs Parallel Computing vs Measured running time

Talk of making code faster mixes up a better method, more hardware and a stopwatch result. Ask whether you are describing how work grows with n, what the steps are, how many processors share them, or how long one run took.

Algorithm Efficiency

Meaning
Algorithm efficiency describes how the steps or memory an algorithm needs grow as the input size n grows, written in Big-O.
Key test
The answer is a growth class like O(n), not a number of seconds.
Formula
T(n)≤c⋅f(n) for n≥n0
Example
Checking every pair in a list of n names is O(n2): 10 names give 45 pairs, 1,000 names nearly 500,000.

Algorithm

Meaning
An algorithm is the step-by-step method itself, judged first on whether it always gives the right answer.
Key test
Asks what the steps are and whether they are correct.
Formula
output=f(input)
Example
Selection sort: find the smallest item, move it to the front, then repeat on the rest.

Parallel Computing

Meaning
Parallel computing splits work across several processors that run at the same time.
Key test
Speed comes from more workers, not from a better growth rate.
Example
With 4 cores, an O(n2) job can finish up to 4 times sooner but is still O(n2).

Measured running time

Meaning
Measured running time is the number of seconds one program takes on one computer with one input.
Key test
A single timed run, affected by the hardware and the input.
Example
A program takes 0.8 seconds to sort 10,000 numbers on a school laptop.

Formula & Notation

How to read it: Big O notation O(f(n)) describes the upper bound on growth rate. n is the input size, and T(n) is the running time as a function of n.

Worked Examples

Example 1 — Count comparisons, then classify

Easy

For a list of n numbers, Method A finds the largest by comparing a running maximum with each number in turn. Method B checks for duplicates by comparing each number with every number after it. Count the comparisons each makes for n = 10 and n = 20, and give each method's Big-O class.
Show the steps and the answer
  1. Method A: the running maximum starts as the first number and is compared with each of the other n − 1 numbers: 9 comparisons for n = 10, 19 for n = 20.

    One loop over the list means one comparison per item, give or take one.

  2. Method B: the first number is compared with the 9 after it, the next with 8, and so on: 9+8+⋯+1=45 for n = 10, and 19+18+⋯+1=190 for n = 20.

    This is a loop inside a loop: each item starts its own pass through the items after it, giving n(n−1)/2 comparisons.

  3. Compare growth: doubling n took A from 9 to 19 (about ×2) and B from 45 to 190 (about ×4).

    Work that doubles with the input is the signature of linear growth; work that quadruples is the signature of quadratic growth.

  4. Drop constants and smaller terms: n−1 is O(n), and n(n−1)/2=12n2−12n is O(n2).

    Big-O keeps only the term that dominates for large n and ignores its coefficient.

Answer: A: 9 and 19 comparisons, O(n). B: 45 and 190 comparisons, O(n2).

Takeaway: One pass over the data is linear; a loop inside a loop over the same data is quadratic. Doubling n shows which one you have.

Example 2 — When the worse Big-O wins

Standard

Method P takes 100n steps and method Q takes n2 steps. Which is faster for n = 50? For n = 1,000? At what size do they cost the same?
Show the steps and the answer
  1. At n = 50: P takes 100 × 50 = 5,000 steps and Q takes 502=2,500.

    Q is twice as fast here even though O(n2) is the worse class, because P carries a large constant, 100.

  2. At n = 1,000: P takes 100,000 steps and Q takes 1,000,000.

    Now P is ten times faster. From n = 50 to n = 1,000, Q's cost grew 400 times and P's only 20 times.

  3. Find the crossover: 100n=n2 when n=100.

    Below 100 items Q wins; above 100, P wins and its lead keeps growing.

  4. Check at n = 100: P takes 100 × 100 = 10,000 steps and Q takes 1002=10,000.

    Equal costs at n = 100 confirm the crossover.

Answer: Q is faster at n = 50 (2,500 vs 5,000 steps); P is faster at n = 1,000 (100,000 vs 1,000,000). They cost the same at n = 100.

Takeaway: Big-O predicts the winner for large inputs only. For small inputs, compare the actual step counts with their constants.

Example 3 — Find the mistake: nested loops counted as one

Application

This code counts pairs that add up to a target: for i from 0 to n − 1: for j from 0 to n − 1: if a[i] + a[j] == target, add 1 to count. Ravi writes: "There is only one variable, n, so this is O(n)." Find the mistake and correct it.
Show the steps and the answer
  1. Count the inner loop: for one value of i, j runs through all n values, so n checks.

    The inner loop starts again from 0 every time the outer loop moves on.

  2. Count the outer loop: i takes n values, each bringing n checks, so n×n=n2 checks.

    Nested loops multiply their counts.

  3. Put in sizes: n = 1,000 gives 1,000,000 checks, and n = 2,000 gives 4,000,000.

    Doubling n quadrupled the work, which an O(n) method never does.

  4. Compare two loops placed one after the other over the same list: n + n = 2n checks, which really is O(n).

    Counting variables cannot tell these two shapes apart; counting how often the innermost line runs can.

Answer: The innermost line runs n2 times, so the code is O(n2), not O(n).

Takeaway: Count how many times the innermost line runs. Nested loops multiply; loops in sequence add.

Where You'll See It

  • Finding a friend's name in a class list

    Reading every name from the top scales with the list length (O(n)): a list twice as long takes about twice as long. Using a sorted list and jumping to the middle each time (O(log⁡n)) barely grows even when the list gets huge.

  • Comparing every pair of students for a handshake

    If everyone shakes hands with everyone else, doubling the class roughly quadruples the handshakes (O(n2)). That quadratic growth is why an algorithm that's fine for 10 items can be hopeless for 10,000.

  • Loading a game level instantly vs. lagging

    A game that searches assets with an efficient method stays fast as levels get bigger, while an inefficient O(n2) method that's fine in a tiny demo can freeze on a full-size map.

Common Mistakes

  1. The slip: Big-O tells you the exact running time of an algorithm.

    Why it's tempting: It uses precise-looking math like O(n), so it feels like an exact count.

    Instead: Big-O describes the growth rate (an upper bound) as input grows; it ignores constant factors and low-order terms. O(n) means 'grows roughly proportionally to n', not 'takes exactly n steps'.

  2. The slip: An algorithm with a better Big-O is always the faster choice.

    Why it's tempting: A smaller growth rate sounds strictly better in every case.

    Instead: For small inputs, constant factors and overhead matter; an O(n2) method can beat an O(nlog⁡n) one on tiny lists. The better Big-O wins as n gets large.

  3. The slip: A loop inside a loop is still just O(n) because there's one variable, n.

    Why it's tempting: Only one input size is named, so it seems like a single pass.

    Instead: Multiply the work of nested loops: a loop running n times inside another loop running n times does about n×n=n2 operations, so it is O(n2).


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Give the Big-O class of each operation count: 3n+7, 5n2+2n+1, and 100.

    Hint: Keep the fastest-growing term and drop constant factors.

  2. A loop over n items contains another loop over the same n items. For n=1000, about how many times does the inner body run, and what is the Big-O?

    Hint: Multiply the number of outer passes by the inner passes.

  3. Binary search halves a sorted list at each step. Starting with 1,024 names, how many halvings leave just 1 name? How many for 1,048,576 names?

    Hint: Write each list size as a power of 2.

  4. Algorithm A takes 100n steps and algorithm B takes n2 steps. Compare them at n=50 and n=500. For which n is A faster?

    Hint: Find where 100n=n2.

  5. An algorithm runs in O(log⁡n) time but makes a full copy of its n-item input. A question asks about its extra memory. Is that time or space complexity?

    Hint: Is the question about steps taken or memory used?

  6. A student says: "If I double n, an O(n2) algorithm takes twice as long." Correct it.

    Hint: Replace n with 2n in n2.

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Why does Big-O drop constants, when 2n is clearly twice as much work as n?

Because the constant depends on details Big-O is meant to ignore, such as how fast the computer is or how many machine instructions one step takes. Doubling the constant is like using a computer half as fast; changing n to n2n^2 is a different kind of growth that no hardware upgrade fixes. For a fixed, small input the constants can matter more, so measure.

What is the difference between worst case, best case and average case?

They describe different inputs of the same size. Linear search through n items takes 1 check in the best case, when the target is first, n checks in the worst case, when it is last or missing, and about n/2n/2 on average when it is present. Big-O is usually quoted for the worst case, because that gives a promise that holds for every input.

What does O(1) mean?

Constant time: the work does not grow with n at all. Reading arr[500] from an array takes the same time whether the array holds 1,000 items or a billion, because the computer jumps straight to the position. O(1)O(1) does not mean one step or instant; it means a fixed amount of work, however large that fixed amount is.

Is exponential growth really that bad?

Yes, once n gets moderate. An algorithm that tries every subset of n items does 2n2^n checks: 20 items give about a million, 40 give about a trillion, and 60 give more than a billion billion. Each extra item doubles the work, so a computer a thousand times faster handles only about 10 more items. This is why some problems are called intractable.

Learning Path

← Before

Algorithm
Algorithm Efficiency

You are here

Start with Algorithm: a precise list of steps you can count. Efficiency adds a way to describe how that count grows with input size, from O(1) through O(log⁡n) and O(n) to O(n2), and to compare methods before running them. Next, Searching and Sorting are where these classes matter most: linear vs binary search, bubble sort vs merge sort.

See Also