Big O Notation for an Algorithm

Question

I can't solve a problem; can someone help me?

What is the Big O notation for the below statement:-

for (int i=2;i<=n;i=i*4)
    sum++;

Answer 1

Once i grows exponentially, it is O(log(n)).

If n is 16 times larger, it is expected to run the loop only two more times than it would.

Answer 2

Once you know that the starting point and multiplier for i are > 1, their exact values make no difference in big-O terms (they only translate into constants added to or multiplying the core component, O(log N), and such constants are neglected in big-O reasoning -- that's the core point of big-O reasoning, after all!!!).

Answer 3

Try counting the number of loops for a few (small) values of n, then graphing the result (n on horizontal axis, loop count on vertical axis). Playing around with a problem is great when you're first learning.

Depending on which values you pick for n, you may not see the pattern. For instance, the loop count is the same for n=10 and n=20. Considering when the loop count will change will also reveal a pattern which can tell you the big-O timing.

Once you have a better understanding of algorithm timing, you won't need to go through this somewhat time-consuming procedure. You'll be able to figure out the big-O timing algebraically through code analysis.

Answer 4

The way I think of big O notation is how long does it take to complete, which is complexity. For example if you have a bubble sort, as you go to items to be sorted it take approximately n*n operations to complete, which is O(N^2).

For binary search, as you increase n in size, you have log2(n) opertions to find the value. Since the number of operation is in terms of log then O(log N) for binary search (where log is log of 2).

For what you have, has increase you have N number of operations (this is even if you offseting) as it is inreasing in a linear fashion, which is O(N). This is the notation for linear search as it may take n/2 options an average to find a value, it is still O(N).

I would look at Wikipedia on O(N) notation. It has a more techinal explaination, and more big O notation information.

Answer 5

Since you are doing this as a homework exercise, what you really need to do is go back to first principles; i.e. the mathematical definition of O notation. Work out how many simple computation steps there are as 'n' increases, work out the limit algebraically, and then proceed to the answer.

In practice, most folks estimate the 'O' complexity, based on knowledge of classical examples and a experience. And quite often they get it wrong.

Answer 6

Assuming that "sum++" is constant which is a pretty reasonable assumption the algorithm is O(log₄ n).

Because the loop goes from 2 to n, you know it is at most O(n). However, because your incremented is multiplied by 4 every loop, there is exponentially less time spent in the loop.

Answer 7

The first 4 values of i are 2, 8, 32, 128 so the formula that shows how many iterations that loops will go through is:

((log(n)/log(2))/2)+0.5