HM1111 algorithm
CSE 2321 HOMEWORK 7
1. Determine the running time of the following algorithm. Write summations to represent loops and solve using bounding. Be sure to show work on both the upper bound and lower bound,
justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer.
Func1(𝑛)
1 𝑠 ← 0;
2 for 𝑖 ← 𝑛 to 𝑛
2 do
3 for 𝑗 ← 1 to 𝑖 do
4 for 𝑘 ← 9𝑛 to 10𝑛
2 do
5 for m ← 𝑖 to 𝑘
6 𝑠 ← 𝑠 + 𝑖 − 𝑗 + 𝑘 − 𝑚;
7 end
8 end
9 end
10 end
11 return (𝑠);
2. Find the running time for each of the following algorithms. Show work by finding a table of values for each while loop, writing the summations, then solving. Be sure to show work on
both the upper bound and lower bound, justify the split, and check that the bounds differ by only a constant factor. Use asymptotic notation to write the answer. a) Func2(n)
1 𝑠 ← 0;
2 𝑗 ← 7𝑛
2
;
3 while (𝑗 > 8) do
4 𝑠 ← 𝑠 + 𝑖 − 𝑗;
5 𝑗 ← ⌊𝑗/9⌋;
6 end
7 return (𝑠);
b) Func3(𝑛)
1 𝑠 ← 0;
2 𝑖 ← 𝑛;
3 while (𝑖 < 5𝑛
3
) do
4 𝑗 ← 7𝑛
2
;
5 while (𝑗 > 8) do
6 𝑠 ← 𝑠 + 𝑖 − 𝑗;
7 𝑗 ← ⌊𝑗/9⌋;
8 end
9 𝑖 ← 4 × 𝑖;
10 end
11 return (𝑠);
c) Func4(𝑛)
1 𝑠 ← 0;
2 for 𝑖 ← 1 to 5𝑛 do
3 𝑗 ← 3𝑖;
4 while (𝑗 < 𝑖
3
) do
5 𝑠 ← 𝑠 + 𝑖 − 𝑗;
6 𝑗 ← 5 × 𝑗;
7 end
8 end
8 return (𝑠);
3. Give the asymptotic complexity of each of the following functions in simplest terms and then order the functions by asymptotic dominance. That is, produce a permutation, f1(n),
f2(n), … , such that fi(n) = O(fi+1(n)). Note if any two functions are asymptotically equivalent, i.e., if fi (n) = Θ(fi+1(n)). Note: ‘lg x’ is a simpler notation for ‘log2 x’.
• fa(n) =n4
lg n4 + lg n2 ;
• fb(n) = 3n+1 + 4n
• fc(n) = 6n0.2 + 3n0.8
• fd(n) = 2
• fe(n) = 4 lg (n2 + 2n) + 6n0.7
• ff(n) = n5 + 1010lg (n+100)
• fg(n) = 3n lg (n2 + 2) + n2
• fh(n) = ((9n2
)( 6n)(121))1/2
• fi(n) = (4n5 + 5n2 + lg n5
)
1/2
• fj(n) = 400
