Complexity of a basic algorithm?

Question

I have this example algorithm:

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

The book I am reading, "Building Java Programs - a Back to the Basics Approach" tells me that I need to find this:

Approximate the runtime of the following code fragment, in terms of n: Write your answer in a format such as O(N^2) or O(N log N).

I don't seem to understand how to get from point a to point b here. I figured two statements = O(2), and a loop with two statements = O(2N) so it should be O(2N + 2). Where am I going wrong?

possible duplicate of Big-O value for iteration sof a while loop — Paul Hankin
– Paul Hankin, Commented Nov 24, 2014 at 1:23

yts · Accepted Answer · 2014-11-24 02:22:03Z

4

When determining complexities, we don't include constants or coefficients. Instead of O(2N + 2), it should be O(n). We only care about numbers if they're exponential, i.e. 2^n or n^2, log2(n), etc.

Putting that aside, are you sure this is O(n)? O(n) would mean that it runs n times, but it looks like j is going to catch up to n before n times. See what I'm saying?

EDIT: Ok, here's what's going on.

Look what happens with j. j = j * 2. j is doubling every time. In other words, the difference between j and n is being halved. When the number of iterations remaining is halved on every iteration, that's called a log(n) algorithm. log(n) algorithms are pretty awesome because even if n is extremely large, log(n) is surprisingly small. Plug some numbers in to see what I mean.

edited Nov 24, 2014 at 2:22

answered Nov 24, 2014 at 1:08

yts

1,9001 gold badge15 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

yts Over a year ago

@Andrew Well look at how fast j is growing each time. How would you describe it in English? Once you know that, you should be able to figure out how to write it in Big O, either by having learnt it in the book or googling. Or asking us :)

yts Over a year ago

@Andrew figure it out yet? Let me know if you're having difficulty.

Andrew Over a year ago

Yeah I havn't figured it out and I've been trying for hours. I'm using an online thing called "Practice-it" but it doesn't give feedback, only right or wrong.

Balint Pato · Accepted Answer · 2014-11-24 01:16:52Z

0

In order to determine the complexity, you are on the right track with trying to find the number of operations! What I usually do if I can't pull up the formula immediately: I find examples first. Try it out for n = 5, n = 8, n=64, n=65 and come up with the number of steps taken, and you'll see soon the pattern!

The formula for number of operations you'll come up with can be very precise, but you can leave the constants out to determine the order of complexity (multipliers and additional constants), as in the end O(2n) is roughly the same as O(3n)compared to O(n^2).

answered Nov 24, 2014 at 1:16

Balint Pato

1,5491 gold badge14 silver badges30 bronze badges

Comments

Zim-Zam O'Pootertoot · Accepted Answer · 2014-11-24 01:26:37Z

0

The loop does not iterate through every value from 1 to N, which is where your O(2N) is going wrong.

It might help to visualize the runtime if you substitute the program with the following, which will have the same complexity - this is similar to algorithms that halve the input size on each iteration

int j = n;
while(j > 1) {
  j = j / 2;
}

edited Nov 24, 2014 at 1:26

answered Nov 24, 2014 at 1:08

Zim-Zam O'Pootertoot

18.2k4 gold badges45 silver badges71 bronze badges

Comments

Makoto · Accepted Answer · 2014-11-24 01:29:10Z

I'd say break it down; this sort of problem looks deceptively straightforward at once, but proving it out would be valuable.

Let's assume n = 100.

First iteration: sum = 1, j = 2
Second iteration: sum = 2, j = 4
Third iteration: sum = 3, j = 8
Fourth iteration: sum = 4, j = 16
Fifth iteration: sum = 5, j = 32
Sixth iteration: sum = 6, j = 64
Seventh iteration: sum = 7, j = 128 # end of iterations.

If this ran in O(N) time, then you would expect about a hundred iterations. We instead increase j by a factor of 2 every time instead, reaching the terminal iteration after about seven times.

That said, we iterate at least once (for n > 1), plus the floor of log(100)/log(2) = 6, for a total of 7 times.

I am inclined to believe that, based on running this little test, that the runtime of this is O(log(n)), and not O(n).

Recall from this graph; logarithms grow much slower over time given large values of N. Even with n = 1000, you would only see 10 iterations.

rask004 · Accepted Answer · 2014-11-24 01:36:46Z

0

Your question asks to approximate the time, an exact time or formula is not required.

Also, Big O Notation, e.g. O(N), tends to be simplified to the most dominant term only (i.e. the term of N whereby if N is very large, that term alone would provide an exact or nearly exact answer).

So, if your exact formula were, say, 4N^2 + 9N + 7, your answer would be O(N^2). Because if N was very large, the N^2 term alone would be enough to approximate the answer.

Also, yts has a point about the j variable, as it's changing exponentially, so from your code the time, t will be:

t = 2(sum) + 2 = 2(log2(n)+1) + 2

Therefore your solution is maybe, of the form O(log N), or perhaps O(log2 N)?

edited Nov 24, 2014 at 1:36

answered Nov 24, 2014 at 1:18

rask004

5806 silver badges15 bronze badges

Collectives™ on Stack Overflow

Complexity of a basic algorithm?

5 Answers 5

3 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related