Write a recurrence relation describing the worst case running time of the follow

Question

Write a recurrence relation describing the worst case running time of the following algorithm and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using substitution/expansion. You may not use the Master Theorem as justification of your answer. Simplify and express your answer as theta(n^k) or theta(n^k log_2 n) whenever possible. If the algorithm is exponential just give exponential lower bounds.

function func(A, n)

if n < 5 then return A(1)

else

for i = 1 to n

for j = i to n-1

A (j) leftarrow A (j) + A (i) + 3

/* endfor */

/* endfor */

y leftarrow func(A, n-5)

return (y)

The recurrence relation for this algoritm is: T(n) = cn^2 + T(n-5)

How is this calculated?

Explanation / Answer

for loop with iterator i runs for n times, and inner loop runs

n + n-1 + n-2 + ... + 1 = n*(n+1)/2 = c*n^2 times.

at each function call, it recursively calls itself with n-5. Therefore, it results in given recurrence relation.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.