A complete guide to solving Recurrence Relations without the Master Theorem. This download includes detailed solutions for 10 algorithmic problems using the Expansion Method and Recursion Tree Analysis, covering linear decrease, divide-and-conquer, and exponential branching complexity patterns.
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) ∈ Θ(?).
