Analysing a small recursive algorithm

Question

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
– Raphael, Commented Mar 9, 2016 at 1:14

Yuval Filmus · Accepted Answer · 2016-03-08 20:22:43Z

1

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$).

answered Mar 8, 2016 at 20:22

Yuval Filmus

281k27 gold badges320 silver badges518 bronze badges

Add a comment |

Stack Exchange Network

Analysing a small recursive algorithm

1 Answer 1

Your Answer

Linked

Hot Network Questions

Analysing a small recursive algorithm

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions