# Analysing a small recursive algorithm

I need to calculate the complexity of func5, depending on variables $n, m$.

func4 is a function whose complexity is $\Theta(n+m)$

void func5(int a[], int n, int m, int b[])
{
if (n==0) { return; }
*b = func4(a,n,m);
func5(a+1,n-1,m,b+1);
}


I get an expression which looks like:

$$C_1*n + C_2*(nm+n^2) - C_2(1+2+3+..n)$$

$C_1$ is the operations done in each iteration of func5,
$C_2$ is the operations done in each call to func4,
and the substraction comes since func4 is receiving each time a smaller $n$ by one.

The answer says that complexity is $\Theta(n*m+n^2)$ but I don't understand how to find the constants leading to Big-Theta notation.

Thanks.

• You have not dealt with the recursion properly. See our reference question for how it works. Also, be mindful of Landau notation in two parameters; it's not clear what $\Theta(n + m)$ "simplifies" to in the case of $n=0$! – Raphael Mar 9 '16 at 1:14

Since $1+2+\cdots+n = \frac{n(n+1)}{2}$, your expression is equal to $$C_1 n + C_2 (nm+n^2) - C_2 \frac{n^2+n}{2} = C_2(nm+n^2/2) + (C_1-C_2/2)n.$$ This shows that for constant $m$ and large enough $n$, your expression is at least $(1/2-\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \geq C_2/2$, even for $\epsilon = 0$), and at most $(1+\epsilon)C_2(nm+n^2)$ (for any $\epsilon > 0$ and, if $C_1 \leq C_2/2$, even for $\epsilon = 0$).