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.
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 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.
Name |
---|
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)