SME
Data Structures & Algorithms
Big-O analysis
Use this for “A quadratic algorithm takes 1 s for 1000 items. About how long for 4000?”
Table
Second size (n₂)
Second time (T₂)
(s)
T₂ against n₂, worked out for every n₂ from 1,000 to 32,000
Time ratio R = 16
This is an example. Type your own values to start a new problem.
p
Power of n
example
g
Power of log n
example
n₁
First size
example
T₁
First time
example
n₂
Second size
example
R
Time ratio
calculated
T₂
Second time
calculated
Formulas
R
=
(
n₂
n₁
)
p
×
(
log₂(
n₂
)
log₂(
n₁
)
)
g
16
=
(
4,000
1,000
)
2
×
(
log₂(4,000)
log₂(1,000)
)⁰
T₂
=
R
×
T₁
16 = 16 × 1
Assumptions
•
The running time is about C × nᵖ × (log₂n)ᵍ: the leading term dominates at these sizes.
•
The constant C is the same for both runs, so it cancels in the ratio of the times.
•
Doubling n multiplies a linear time by 2, a quadratic one by 4 and a cubic one by 8.
Step-by-step
WE KNOW
p = 2, g = 0, n₁ = 1,000, T₁ = 1 s, n₂ = 4,000
FIND
time ratio (R), second time (T₂)
Step 1 · Find time ratio (R)
Use R = (n₂ ÷ n₁)ᵖ × (log₂(n₂) ÷ log₂(n₁))ᵍ
The constant cancels, so the times scale as the growth function at the two sizes.
R
=
(
n₂
n₁
)
p
R
=
(
4,000
1,000
)
2
R
=
4
2
R
=
16
Step 2 · Find second time (T₂)
Use T₂ = R × T₁
The
second
run
takes
R
times
as
long
as
the
first.
T₂
=
16
×
1
T₂
=
16
s
Check
Put the numbers back in. Both sides should match.
16
=
(
4,000
1,000
)
2
×
(
log₂(4,000)
log₂(1,000)
)⁰
✓
16 = 16 × 1 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
The master theorem
Use this for “Solve T(n) = 8T(n ÷ 2) + Θ(n²) with the master theorem.”
Counting nested loops
Use this for “For i from 1 to 100 and j from 1 to i − 1, how many times does the inner body run?”
Ordering growth rates
Use this for “Order n², log n, 2ⁿ, n log n, √n, n!, 1 and n from slowest to fastest growth.”