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); 

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.


  • $\begingroup$ 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$! $\endgroup$ – 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$).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.