SME
Data Structures & Algorithms · Problem type
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?”
This is an example. Type your own values to start a new problem.
Nfull
=
n
2
Nₚₐᵢᵣₛ
=
×
(
−
1)
2
Nₜᵣᵢₚₗₑₛ
Runs with i < j < k
worked out (not typed)
Formulas
Nfull
=
n
2
10,000
=
100
2
Nₚₐᵢᵣₛ
=
n
×
n
− 1
2
4,950
=
100
×
100 − 1
2
Nₜᵣᵢₚₗₑₛ
=
n
×
(
n
−
1)
×
n
− 2
6
161,700
=
100
×
(100
−
1)
×
100 − 2
6
Assumptions
•
The body costs the same each time, so the running time is its count times that cost.
•
Two full loops, i and j each from 1 to n, run the body n × n = n² times.
•
Loops with j < i run once for each pair: C(n, 2) = n(n − 1) ÷ 2 times, about half of n².
•
Three loops with i < j < k run once for each set of three: C(n, 3) times, about n³ ÷ 6.
Step-by-step
WE KNOW
n = 100
FIND
full double loop (Nfull), runs with j < i (Nₚₐᵢᵣₛ), runs with i < j < k (Nₜᵣᵢₚₗₑₛ)
Step 1 · Find full double loop (Nfull)
Use Nfull = n²
The
inner
loop
runs
n
times
for
each
of
the
n
outer
passes.
Nfull
=
100
2
Nfull = 10,000
Step 2 · Find runs with j < i (Nₚₐᵢᵣₛ)
Use Nₚₐᵢᵣₛ = n × (n − 1) ÷ 2
Pass
i
runs
the
inner
body
i
−
1
times:
0
+
1
+
…
+
(
n
−
1),
which
is
n
(
n
− 1)
2
.
Nₚₐᵢᵣₛ
=
100
×
100 − 1
2
Nₚₐᵢᵣₛ
=
100
×
99
2
Nₚₐᵢᵣₛ
=
9,900
2
Nₚₐᵢᵣₛ = 4,950
Step 3 · Find runs with i < j < k (Nₜᵣᵢₚₗₑₛ)
Use Nₜᵣᵢₚₗₑₛ = n × (n − 1) × (n − 2) ÷ 6
Each
run
picks
three
different
values
in
increasing
order,
one
set
of
three:
C(
n
,
3).
Nₜᵣᵢₚₗₑₛ
=
100
×
(100
−
1)
×
100 − 2
6
Nₜᵣᵢₚₗₑₛ
=
100
×
99
×
98
6
Nₜᵣᵢₚₗₑₛ
=
9,900
×
98
6
Nₜᵣᵢₚₗₑₛ
=
970,200
6
Nₜᵣᵢₚₗₑₛ = 161,700
Check
Put the numbers back in. Both sides should match.
10,000
=
100
2
✓
4,950
=
100
×
100 − 1
2
✓
161,700
=
100
×
(100
−
1)
×
100 − 2
6
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.