# Reccurence of recursive function with unequal sizes of subproblems [duplicate]

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?

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.
The size of the problems aren't $\frac{1}{3}$ & $\frac{2}{3}$. The size of the two subproblems are $\frac{1}{3}$each, so $b=3$.
I have overlooked that the second recursive call only takes the latter $\frac{1}{3}$ of the problem instead of the latter $\frac{2}{3}$.