Reccurence of recursive function with unequal sizes of subproblems Given pseudocode:

X is an array

function FUN(X)
    l = length(X)
    if l &lt;= 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) &amp;= 2T\left(\frac{n}{3}\right)+1\\
 &amp;= 2\left(2T(\frac{n}{3^2})+1\right)+1=2^2\ T\left(\frac{n}{3^2}\right)+2+1\\
 &amp;=2^3\ T\left(\frac{n}{3^3}\right)+4+2+1 &amp;\text{and, in general, we have}\\
&amp;\dotsc\\
&amp;=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.