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

Big-O notation describes the asymptotic growth of an algorithm's cost as input size increases — most often applied to worst-case running time or memory, expressed as $O(n)$ , $O(n^2)$ , $O(\log n)$ , etc.

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?

Algorithm A: steps at n=10 vs n=20 (quadratic growth)

Answer

Algorithm B is more efficient:

O(n)

O(n^2)

First step

Step 1: Algorithm A: when size doubles (10→20), steps quadruple (100→400). This suggests

O(n^2)

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

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.

Example 3

medium

A function builds a list of

n

items by repeatedly prepending. Each prepend on a linked list is

O(1)

; on a Python list it is

O(n)

. What total complexity in each case?

Example 4

medium

A function does

3n + 5

operations. What is the Big-O, and why don't constants matter asymptotically?

Example 5

medium

Two algorithms have time complexities

O(n^2)

and

O(100n)

. For which

n

does the linear algorithm overtake the quadratic in operation count?

Example 6

hard

Quicksort's average-case is

O(n \log n)

but worst-case is

O(n^2)

. Name two engineering tweaks that keep the worst case rare in practice.

Example 7

hard

BFS and Dijkstra both visit vertices in graph order. On a graph with

V

vertices and

E

edges, what are their respective complexities, and why does Dijkstra need the extra log factor?

Example 8

hard

An algorithm has time complexity

O(n \log n)

and space

O(n)

. List one practical concern beyond Big-O that affects real-world efficiency.

Example 9

hard

A naive matrix multiplication is

O(n^3)

. State two complexity-class improvements and the historical names.

Example 10

challenge

Knuth: 'Premature optimization is the root of all evil.' Explain the engineering principle behind the quote in the context of

O(n)

O(\log n)

Example 11

hard

A function processes a stream of

n

items and must report the median after each insertion. What's the most efficient achievable per-operation complexity, and the data structure that achieves it?

Example 12

medium

An algorithm runs in

T(n) = 1000n

ms and another in

U(n) = n^2

ms. Which is faster when

n = 10

? When

n = 10000

T(n)=1000n is faster for n>1000; crossover with U(n)=n² is at n=1000

Example 13

medium

Merge sort runs in

O(n \log n)

. Roughly how many operations does it perform on

n = 1{,}048{,}576 = 2^{20}

items?

Merge sort O(n log n): at n=2²⁰ ≈ 1M items, only ~20 million operations

Example 14

medium

A function calls a

O(n)

helper inside a loop that runs

n

times. What is the overall time complexity?

Example 15

medium

For

n = 30

, compare

2^n

and

n^2

. Which algorithm class would finish, and which would not?

Example 16

hard

Algorithm A runs in

T_A(n) = 100n

, and algorithm B runs in

T_B(n) = n^2

. For what range of

n

is algorithm B actually faster?

Example 17

hard

A recursive function makes two calls on inputs of size

n/2

and does

O(n)

work outside the calls. What is its time complexity?

Example 18

hard

You scan a list of

n

items and for each item do a

O(\log n)

binary search in a separate sorted list. What is the total time complexity?

Example 19

hard

You must check if any two of

n

numbers sum to a target

T

. A naive double loop is

O(n^2)

. Describe a more efficient approach and give its complexity.

Example 20

challenge

Suppose you have an algorithm with time complexity

O(n \log n)

that takes

1

second on

n = 10^6

. Approximately how long will it take on

n = 10^9

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`.

Algorithm X (n²) vs Algorithm Y (n): quadratic explodes at n=1000

Example 3

easy

A loop runs once per element of an array of size n. What is its Big-O time complexity?

Single loop over n elements: O(n) — iterations match input size exactly

Example 4

easy

Binary search on a sorted array of size n has what time complexity?

Example 5

easy

Two nested loops, each running n times, give what complexity?

Two nested loops each over n: total body executions = n²

Example 6

easy

Accessing `a[5]` in an array by index takes what time, regardless of array size?

Example 7

easy

Does Big-O describe the upper bound or the exact running time?

Example 8

easy

Why does algorithm efficiency matter more as data grows?

Example 9

easy

Which is faster for large n:

O(n)

O(n^2)

O(n) grows much more slowly than O(n²) — linear wins at large n

Example 10

easy

Linear search through n items has what worst-case complexity?

Example 11

medium

An algorithm does `n + n^2` operations. What is its Big-O?

n + n² operations: n² dominates, confirming O(n²)

Example 12

medium

An algorithm does `3n + 5` operations. What is its Big-O?

Example 13

medium

For n = 1,000,000, roughly how many steps does an

O(\log_2 n)

algorithm take?

Binary search step count grows as log₂ n

Example 14

medium

Doubling the input size doubles the runtime. What complexity class is this?

Doubling input doubles runtime — consistent with O(n)

Example 15

medium

Doubling the input size quadruples the runtime. What complexity class is this?

Doubling input quadruples runtime — consistent with O(n²)

Example 16

medium

For small inputs, an

O(n^2)

algorithm beats an

O(n)

one. What does Big-O ignore that explains this?

Example 17

medium

A function loops over an array (n) and, for each element, does a binary search in another sorted array (log n). Total complexity?

Example 18

challenge

Algorithm A is

O(n^2)

with 1 op per step; B is

O(n)

with 100 ops per step. For roughly what n does B become faster?

Algorithm B (100n ops): crossover with A (n²) at n=100

Example 19

challenge

Why is the naive recursive Fibonacci

O(2^n)

rather than

O(n)

Example 20

challenge

Counting sort runs in

O(n + k)

where k is the value range. When does it beat comparison sorts'

O(n \log n)

Example 21

medium

An algorithm halves the input each step until size 1, doing constant work per step. What is its complexity?

Halving algorithm: steps = log₂ n

Example 22

medium

An algorithm does `n^2 + 1000n` operations. What is its Big-O for large n?

Example 23

easy

Doubling the input doubles a hash-table lookup time from

1\mu s

1\mu s

(no change). What complexity is this consistent with?

Example 24

easy

An algorithm has nested loops, the outer over

n

items and the inner over the same

n

items. What is its time complexity?

Example 25

easy

Allocating an array of

n

integers requires what space complexity?

Example 26

medium

Merge sort divides into two halves, sorts each, and merges. Solve

T(n) = 2T(n/2) + O(n)

for the complexity.

Example 27

medium

For

n = 1000

, compare the rough number of operations:

O(n^2)

O(n \log n)

Example 28

medium

A naive recursive Fibonacci has complexity

O(\phi^n)

. Why is memoization a huge win, and what's the resulting complexity?

Example 29

medium

Cache-friendly access: why is iterating a 2D array row-by-row often much faster than column-by-column in row-major languages?

Example 30

hard

A program is I/O-bound — most time is spent waiting on disk. Will switching from

O(n^2)

O(n \log n)

help?

Example 31

hard

Two-sum problem: find indices

i, j

with `arr[i] + arr[j] = target`. What's the brute-force complexity and what's the best?

Example 32

hard

Time-space tradeoff: a precomputed lookup table can answer queries in

O(1)

instead of

O(\log n)

each. When is this worth it?

Example 33

medium

Pseudocode: `for i in 1..n: for j in 1..i: ...`. What is the total inner-body count?

Example 34

medium

Python list `in` membership test is

O(n)

. What single data-structure swap gives

O(1)

membership?

Example 35

challenge

Rank the time complexity classes in order from FASTEST to SLOWEST growth:

O(n!)

O(n^3)

O(\sqrt{n})

O(\log \log n)

O(n^{\log n})

Example 36

easy

What is the Big-O time complexity of a single loop that prints each element of an array of size

n

Example 37

easy

Hashing a key into a hash table to look up a value takes (on average) what time complexity?

Example 38

easy

What is the Big-O of three nested loops each running

n

times?

Example 39

easy

A function does

3n + 5

operations on an input of size

n

. What is its Big-O time complexity?

Example 40

medium

A function has runtime

T(n) = 5n^2 + 20n + 100

. What is its tightest Big-O?

Example 41

medium

What is the time complexity of finding the maximum of an unsorted array of

n

elements?

Example 42

medium

What is the time complexity of bubble sort in the worst case?

Example 43

medium

What is the time complexity of computing the sum of all

n

numbers in an array using a single loop?

Example 44

medium

What is the time complexity of looking up a value by index in an array (e.g., `a[i]`)?

Example 45

hard

What is the time complexity of the following snippet? `for i in 1..n: for j in 1..i: do_work()`

Example 46

hard

What is the time complexity of inserting at the front of an array of size

n

Example 47

hard

A binary-search-tree lookup on a balanced tree has what time complexity? On a maximally unbalanced tree?

← Back to Algorithm Efficiency Practice Mode

Related Concepts

Algorithm Searching Sorting Binary Search Merge Sort

Background Knowledge

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

algorithm