World's most popular travel blog for travel bloggers.

[Solved]: Reccurence of recursive function with unequal sizes of subproblems

, , No Comments
Problem Detail: 

Given pseudocode:

X is an array  function FUN(X)     l = length(X)     if l <= 1 then         PRINT("Hello")         return     end if     p = l / 3     FUN(X[1...p])     FUN(X[(l-p+1)...l]) end function 

I now want to get the reccurence of this pseudocode. At the moment I have $$T(n) = 2 \cdot T(\frac{n}{b})\cdot O(1)$$

but the problem is that I don't know how to handle the fact that the first recursive call has a subproblem size of $\frac{1}{3}$ and the second has a subproblem size of $\frac{2}{3}$. What is $\frac{n}{b}$ then?

Asked By : Basti Funck

Answered By : Rick Decker

Your timing function is $T(n)=2T(n/3)+1$, namely two recursive calls to one-third size problems plus a constant amount of time for the if test and the assignments. If you know the Master Theorem, the answer is immediate, namely $T(n)=\Theta(n^{\log_32})$. If you don't know the MT, it's not too difficult to see the answer by expansion:

$$\begin{align} T(n) &= 2T\left(\frac{n}{3}\right)+1\\ &= 2\left(2T(\frac{n}{3^2})+1\right)+1=2^2\ T\left(\frac{n}{3^2}\right)+2+1\\ &=2^3\ T\left(\frac{n}{3^3}\right)+4+2+1 &\text{and, in general, we have}\\ &\dotsc\\ &=2^k\ T\left(\frac{n}{3^k}\right)+\left(2^{k-1}+\dotsm +4+2+1\right) \end{align}$$ Now let $n=3^k$ and the result follows with a little algebra.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback