You are given the following algorithm written in pseudocode. Compute its worst-case running time (i.e. T(n))...

 

Transcribed Image Text:

You are given the following algorithm written in pseudocode. Compute its worst-case running time (i.e. T(n)) and also give its order of time complexity. Show each step of your solution. METHOD(A) COST WORST-CASE TIMES 1 2 3 5 6 7 8 9 10 total 0 result ← 0 for i 0 to length[A]-1 do if (i % 2 = 0) for j← 1 to length [A]-1 do total total + A[j] A[i] ← total else A[i] A[i]*(-1) result result + A[i] return result a. Solve the following recurrence equation by substitution method. Take O(n²) as your guess. Show all the steps of your solution. T(n) = 8T()+ 8n where T(1) = T(2) = T(3) = 16 b. Draw the recursion tree for recurrence T(n) = T(n-1) + 2n. Solve T(n). You are given the following algorithm written in pseudocode. Compute its worst-case running time (i.e. T(n)) and also give its order of time complexity. Show each step of your solution. METHOD(A) COST WORST-CASE TIMES 1 2 3 5 6 7 8 9 10 total 0 result ← 0 for i 0 to length[A]-1 do if (i % 2 = 0) for j← 1 to length [A]-1 do total total + A[j] A[i] ← total else A[i] A[i]*(-1) result result + A[i] return result a. Solve the following recurrence equation by substitution method. Take O(n²) as your guess. Show all the steps of your solution. T(n) = 8T()+ 8n where T(1) = T(2) = T(3) = 16 b. Draw the recursion tree for recurrence T(n) = T(n-1) + 2n. Solve T(n).

Answer rating: 100% (QA)

1 ... View the full answer