Write a recurrence relation describing the worst case running time of each of th

Question

Write a recurrence relation describing the worst case running time of each of the ms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using either substitution, a recursion tree or induction. You may NOT use the Master theorem. Assume that all arithmetic operations take constant time. following algorith Simplify and express your answer as (nk) or (nk(log n)) wherever possi ble. If the algorithm takes exponential time, then just give exponential lower bounds

Explanation / Answer

reccurence relation:

T(n) = T(n-5)+O(sqrt(n));// inner loop runs upto root n

T(k)=A[1]; where k<=10

T(n) = T(n-5)+n^1/2 <-1

T(n-5)=T(n-10)+(n-5)^1/2 <-2

subtitute 2 in 1

T(n) = T(n-10)+(n-5)^1/2+(n)^1/2

= T(n-15)+(n-10)^1/2+(n-5)^1/2+n^1/2   

=   T(n-p)+(n-p)^1/2 +.............+(n-10)^1/2+(n-5)^1/2+n^1/2

let n-p = k, A[1] =c

= C+(n-p)^1/2 +.............+(n-10)^1/2+(n-5)^1/2+n^1/2

= O(n^5/2)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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