Can anybodyt help to find complexity oof this algo: T(n) = n^ (1/3) T( sqrt( n) ) + 2n
I solved it and found it be O(n) but is it correct? Please confirm.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | cry | 158 |
4 | atcoder_official | 156 |
4 | nor | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
8 | Um_nik | 153 |
10 | djm03178 | 146 |
Can anybodyt help to find complexity oof this algo: T(n) = n^ (1/3) T( sqrt( n) ) + 2n
I solved it and found it be O(n) but is it correct? Please confirm.
Название |
---|
You can keep expanding T(n). By doing this, you get:
The first term is equal to
as n gets large, since the sum in the exponent is a geometric series.
There are only log(log(n)) terms of the other kind. Proof: say that i is the last number for which
. Then
is approximately 2 (or 3, but if it is bigger we can take the root of that to get i+1), so we can take the logarithm from both sides of the equation
. This results in
, so
. Then we find for ![](https://espresso.codeforces.com/20fa54cc8dee35d9e540d71af2d23e4c4c78c600.png)
Every term of that kind have an exponent between 2/3 and 1. Say that we start counting these terms from i=0. Then the i'th term has an exponent equal to
. So as you can see for i=0, this exponent is equal to 1, but as i gets larger, this exponent tends to 2/3.
As n gets larger and larger, there are many more terms with exponents 2/3 than 1. So as n becomes large, the majority of the terms have an exponent which is approximately 2/3. Therefore the complexity of this algorithm is![](https://espresso.codeforces.com/58f183f2e2850e340d6618f2d59740ddc60542bf.png)
Shouldn't the upperbound be n as when exponent at i=0; exponent is 1. O( n + ( ( n^(2/3) ) * log( log(n) ) == O( n )?
Well, O(n) is a bit too small I guess. You could say that it is of order
, because every term is smaller than 2n. I think the actual complexity of this algorithm is of the form
where α is a number between
and 1.
This
complexity differs from
with a maximum factor of 6 for n smaller than 264, so you wouldn't see any difference for 'small' values of n. Still as n gets larger, this factor keeps increasing.
It's
, because
is
and each other summand is
and there is
summands:
, because ![](https://espresso.codeforces.com/a549205262fba5306dadcc6e4f423624716e6b55.png)