Question

Write a recurrence relation describing the worst-case
running time of each of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem.

上午1:46 3月21日周四 令52%. " 5. endfor 6. return (r); function func4(A, n) *Aarray of n integers */ 1. if n s 20 then return (A[n]); 4. while (i < n/2) do 7. endwhile 8. x -x+func4(A, n - 10); 9. return (r);

Answer 1

if n <= 20 it is constant function

Otherwise recurrence relation of above algorithm is

T(n) = T(n-4) + T(n-10) +

log3(n)

So recurrence relation is

T(n) = T(n-4) + T(n-10) + log(n)

As shown in recurrence tree of this algorithm the worst case time complexity will be

O(2"log(n)

22 turm las (n-tu-10) (n-10-40 o-t) h-lo (n-10-4

//If you have any doubt.Please feel free to ask.Thanks.