Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify...

 

Transcribed Image Text:

Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify your solution. When using upper and lower bounds, be sure to justify both the upper bound and lower bound and check that the bounds differ by only a constant factor. 4. Func4(n) S 1 0; for i 4 to 4n do 2 3 for j = 1 to 15i do 4 for k 3 to 10 do 5 ST s + i j + k; 6 end 7 end 8 end 9 return (s); 5. Func5(n) 1 s 0; 2 4 2345 for i for j 4 to n do - 6 to 3i|log2 il do s s + i j; 5 end 6 end 7 return (s); 6. Func6(n) 1 S 0; 2 3 for in to 4n do for j 1 to i do 4 ssij; 5 end 6 end 7 return (s); Determine the running time of the following algorithms. Write summations to represent loops and simplify. Justify your solution. When using upper and lower bounds, be sure to justify both the upper bound and lower bound and check that the bounds differ by only a constant factor. 4. Func4(n) S 1 0; for i 4 to 4n do 2 3 for j = 1 to 15i do 4 for k 3 to 10 do 5 ST s + i j + k; 6 end 7 end 8 end 9 return (s); 5. Func5(n) 1 s 0; 2 4 2345 for i for j 4 to n do - 6 to 3i|log2 il do s s + i j; 5 end 6 end 7 return (s); 6. Func6(n) 1 S 0; 2 3 for in to 4n do for j 1 to i do 4 ssij; 5 end 6 end 7 return (s);