Recursive equation from algorithm

Question

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.

Answer 1

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(n³) work. As a result, your recursive function is more accurately modeled as

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

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