Student Student - 1 month ago 17
Java Question

Showing the order of growth of the function

I have the following code

int sum = 0;
for (int i = 1; i <= n; i = i*2)
{
for (int j = 1; j <=n; ++j)
{
++sum;
}
}


And I have the following analysis which according to some people is wrong even though the answer is correct, but I don't understand why.

So, I do the following,

n = 1; i = 1; j is being executed 1 time
n = 2; i = 2; j is being executed 2* 1 time
n = 3; i = 4; j = 4 * 3 times
n = 4; i = 8; j = 8 * 4 times
n = 5; i = 16; j = 16 * 5 times
......
n = k; i = 2^k; j = n * 2^k times


And since 2^k is log(n)

The order of growth of this function is nlog(n) which is a linearithmic growth rate.

Am I doing something wrong in my analysis? Please let me know if I have any mistakes because it is confusing me a lot. Thank you! I want to apply this analysis to more complicated nested loops, but before I do that I need to know what I'm doing wrong.

And could someone explain me why people are down voting this post? Should I delete it because I'm looking for help and for some reasons some people don't like this post...




Update:

I spent a lot of time by myself trying to figure out why my analysis is wrong. Thanks to @YvesDaoust I think I'm starting to understand it a little bit more.

I will never ask any question on stackoverflow since users here are really hostile and will down vote anything which is wrong or stupid according to them.

I'm really frustrated because of this situation and for those who see this post be aware that if you ask a question be prepared to get down votes for no reason without any explanations.

Answer

The body of the inner loop is executed n times.

The body of the outer loop is executed for all powers of 2 from 1 to n and there are about log2(n) of them, hence the global complexity

O(n.log(n))