What is time complexity of the following snippet? int function_5(int x) {

Question

What is time complexity of the following snippet? int function_5(int x) {

int res = 0;
for (int i = 0; i < x; i++)
{
res += i + function_5(i);
}
return res;
}
i guess it's O(n^2) but it doesn't feel right

0

16.10.2020

4 ответов

10 просмотров

mahdi, the Автор вопроса

void
It's exponential

Can you explain?

0

16.10.2020

void

mahdi, the
Can you explain?

The educational way is to trace what happens when u call f(5), the easiest way is to try with f(1000) and the theoretical is to mess with the formula T(n) = 1 + \Sigma_{x = 0}^{n - 1} T(x) but it's difficult for me to solve it.

0

16.10.2020

void

void
The educational way is to trace what happens when ...

I just realized that the eqn is nothing but T(n) = 1 + 2 * T(n - 1) -_- That is T(n) = O(2^n), clearly exponential.

0

16.10.2020

void · Accepted Answer

void

It's exponential

0

16.10.2020

Похожие чаты

What is time complexity of the following snippet? int function_5(int x) {

4 ответов

Похожие вопросы