Algorithm Efficiency Examples in CS Thinking

Start with the recap, study the fully worked examples, then use the practice problems to check your understanding of Algorithm Efficiency.

This page combines explanation, solved examples, and follow-up practice so you can move from recognition to confident problem-solving in CS Thinking.

Concept Recap

Algorithm efficiency describes how an algorithm's time or memory requirements grow relative to the size of its input, measured using Big O notation. It answers the question: as the input gets larger, how much slower does the algorithm become?

Does doubling the data double the time? Or quadruple it? Or barely change it?

Read the full concept explanation →

How to Use These Examples

  • Read the first worked example with the solution open so the structure is clear.
  • Try the practice problems before revealing each solution.
  • Use the related concepts and background knowledge badges if you feel stuck.

What to Focus On

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

Common stuck point: Big O ignores constant factors—2n and 100n are both O(n) because the growth rate is what matters.

Sense of Study hint: When analyzing efficiency, first identify the input size n. Then count how many times the most-repeated operation executes as a function of n (look for nested loops). Finally, express the growth rate using Big O, dropping constants and lower-order terms.

Worked Examples

Example 1

hard
Algorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10 steps for size 10 and 20 steps for size 20. Which is more efficient and what might their time complexities be?

Solution

  1. 1
    Step 1: Algorithm A: when size doubles (10→20), steps quadruple (100→400). This suggests O(n^2).
  2. 2
    Step 2: Algorithm B: when size doubles, steps double (10→20). This suggests O(n).
  3. 3
    Step 3: Algorithm B is more efficient — it grows linearly while A grows quadratically.

Answer

Algorithm B is more efficient: O(n) vs O(n^2).
Efficiency measures how an algorithm's resource usage (time or space) grows with input size. Linear growth (O(n)) is much better than quadratic (O(n^2)) for large inputs.

Example 2

hard
Explain why binary search (O(\log n)) is more efficient than linear search (O(n)) for a sorted list of 1,000,000 elements.

Practice Problems

Try these problems on your own first, then open the solution to compare your method.

Example 1

hard
Rank these time complexities from most to least efficient: O(n^2), O(1), O(n \log n), O(n), O(2^n).

Example 2

hard
Algorithm X checks every pair of students in a class of size `n`. Algorithm Y checks each student once. Match each algorithm to `O(n^2)` or `O(n)`, and explain which scales better for `n = 1000`.
← Back to Algorithm Efficiency Practice Mode

Related Concepts

Algorithm

Background Knowledge

These ideas may be useful before you work through the harder examples.

algorithm