Похожие чаты

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

4 ответов

3 просмотра

It's exponential

mahdi, the- Автор вопроса
void
It's exponential

Can you explain?

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.

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.

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

Обсуждают сегодня

For managing user-generated content rights in gaming? 🤯🚀
Brian
37
Do we have a Chinese community here?
迪迦
20
@Aiwan что такое база образца?
Alexey
27
Не многие знают, а кто знает, тот уже успел забыть, что в далёком 2004 году эта игра произвела настоящий фурор, настолько революционной была технология, применяемая для её соз...
ICCID
4
Why binance delisting the token?
🅰🅽🅳🆁🅴🆆
14
Hi is Atomic wallet safe to exchange btc to xmr?
Regex
20
Короче я тут узнал полный пиздец Что кучу постов которые я создавал через posted Спустя время не могу редактировать и менять Мол телега возвращае ошибку Это реально так ...
inc.
13
коллеги, добрый вечер! А никто не знает как модальная форма может себя закрыть? Ну допустим модальная форма определила, что смысла ей работать нет и хочет вернуть modalResult...
Михаил
83
Hello, Ergo Investor here. Had a few questions for the leadership of the project, from what I’ve seen @kushti_ru , @Armeanio @dadreboi In one sentence, what is your vision f...
A
16
Is UniBright Freequity an active live product ? A friend here in Asia was discussing the Tokenisation of RWA’s in his case Real Estate as he’s a developer with numerous overs...
Digital Trust
5
Карта сайта