Algorithm Analysis & Time Complexity Solutions: Loop Execution & Asymptotic Notation ( Data Structures and Algorithms )
A comprehensive solution set for analyzing the time complexity of various pseudo-code algorithms. This resource derives exact running time formulas $T(n)$ and determines asymptotic bounds (Theta notation) using integral approximations and summation techniques for nested loops and recursive steps.
1. (Not Graded – Practice Problem)
Analyze the running time of the following algorithm:
1 for i ← 8 to ⌊n
3/2
⌋ do
2 for j ← 40 to i
2
⌊(log4
i)
2
⌋ do
3 x ← x + 1;
4 end
5 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
2. (20 points)
Analyze the running time of the following algorithm:
1 for i ← 2n to 4n
3 do
2 j ← ⌊√
i⌋;
3 while j > 16 do
4 x ← x + 1;
5 j ← j − 5;
6 end
7 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
1
3. (Not Graded – Practice Problem)
Analyze the running time of the following algorithm:
1 for i ← 3n to ⌊n
3/2
⌋ do
2 for j ← 2n to i do
3 x ← x + (i − j + 1);
4 end
5 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
4. (Not Graded – Practice Problem)
Analyze the running time of the following algorithm:
1 for i ← 5 to n
3 do
2 j ← i
2
;
3 while j > 23 do
4 x ← x + 1;
5 j ← ⌊j/7⌋;
6 end
7 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
5. (20 points)
Analyze the running time of the following algorithm:
1 i ← 15;
2 while i ≤ n
3 do
3 for j ← 1 to n
3/i do
4 x ← x + 1;
5 end
6 i ← 7 · i;
7 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
6. (Not Graded – Practice Problem)
Analyze the running time of the following algorithm:
1 i ← 5;
2 while i ≤ n
2 do
3 for j ← 1 to ⌊i/2⌋ do
4 x ← x + 1;
5 end
6 i ← 8 · i;
7 end
2
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
7. (20 points)
Analyze the running time of the following algorithm:
1 i ← 18;
2 while i ≤ n
2.5 do
3 j ← n
2
;
4 while j > 16 do
5 x ← x + 1;
6 j ← j − ⌈√
n⌉;
7 end
8 i ← 5 · i;
9 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
8. (20 points)
Analyze the running time of the following algorithm:
1 i ← n;
2 while i ≥ 15 do
3 j ← 12;
4 while j < 5i do
5 x ← x + 1;
6 j ← j + 8;
7 end
8 i ← ⌊i/3⌋;
9 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
9. (20 points)
Analyze the running time of the following algorithm:
1 for i ← 75 to n
2 step 12 do
2 for j ← 6 to 5i do
3 x ← x + 1;
4 end
5 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
3
10. (Not Graded – Practice Problem)
Analyze the running time of the following algorithm:
1 i ← n
2
;
2 while i ≥ 15 do
3 j ← 6;
4 while j < i4 do
5 x ← x + 1;
6 j ← j + i;
7 end
8 i ← ⌊i/5⌋;
9 end
(a) Write a formula for the running time T(n).
(b) Simplify to get T(n) ∈ Θ(?).
