CODEWITHSUNDEEP
algorithmrecursionpseudocoderecurrence
Patrick
Patrick

Reputation: 149

Recursive equation from algorithm

I started my masters degree in bioinformatics this October, for a former biologist finding a recursive equation from a piece of code is pretty hard. If somebody could explain this to me, i would be very grateful.

How do i find a recursive equation from this piece of code?

procedure DC(n)
   if n<1 then return
   for i <- 1 to 8 do DC(n/2)
   for i <- 1 to n³ do dummy <- 0

My guess is T(n) = c + 8T(n/2), because the first if condition needs constant time c and the first for loop is the recursive case which performs from 1 to 8, therefore 8*T(n/2), but I dont know how to ad the last line of code to my equation.

Upvotes: 1

Views: 387

Answers (2)

user2736738
user2736738

Reputation: 30926

This turns out to be T(n)= 8*T(n/2)+O(n^3).

I will give you a jab at solving this with iteration/recursion tree method.

T(n) = 8* T(n/2) + O(n^3)
     ~ 8* T(n/2) + n^3
     = 8*(8* T(n/4) + (n/2)^3))+n^3
     = 8^2*T(n/4)+8*(n/2)^3+ n^3
     = 8^2*T(n/2^2)+n^3+n^3
     = 8^2( 8*T(n/8)+(n/4)^3)+n^3+n^3
     = 8^3*T(n/2^3)+ n^3 + n^3 + n^3
     ...
     = 8^k*T(n/2^k)+ n^3 + n^3 + n^3 + ...k time ...+n^3

This will stop when n/2^k=1 or k=log_2(n).

So the complexity is O(n^3log(n))

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372764

You’re close, but that’s not quite it.

Usually, a recurrence relation only describes the work done by the recursive step of a recursive procedure, since it’s assumed that the base case does a constant amount of work. You’d therefore want to look at

  • what recursive calls are made and on what size inputs they’re made on, and
  • how much work is done outside of that.

You’ve correctly identified that there are eight recursive calls on inputs of size n / 2, so the 8T(n / 2) term is correct. However, notice that this is followed up by a loop that does O(n3) work. As a result, your recursive function is more accurately modeled as

T(n) = 8T(n / 2) + O(n3).

It’s then worth seeing if you can argue why this recurrence solves to O(n3 log n).

Upvotes: 2

Related Questions