Big O Notation Homework--Code Fragment Algorithm Analysis?

Question

For homework, I was given the following 8 code fragments to analyze and give a Big-Oh notation for the running time. Can anybody please tell me if I'm on the right track?

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

I'm thinking O(N) for fragment 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O(N) for fragment 2 as well

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O(N^2) for fragment 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O(N) for fragment 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O(N^2) for fragment 5 but the n * n is throwing me off a bit so I'm not quite sure

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O(N^2) for fragment 6 as well

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O(N^3) for fragment 7 but once again the n * n is throwing me off

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O(N) for fragment 8

I disagree with the "too localized" comment. Calculating Big-Oh is a central part of algorithm analysis. Specific code examples with estimates of Big-Oh can be extremely valuable to folks who are trying to become fluent in this area. — JESii, Sep 25 '13 at 22:53

Kyle Cronin · Accepted Answer · 2008-10-20T18:22:57.723

20

I think fragment 5 is O(n^3), and similarly fragment 7 is O(n^5)*. It also looks like O(log(n)) for fragment 8.

For the n * n problems, you have to execute the body of the loop n * n times, so it would be O(n^2), then you compound that with the order of the other code. Fragment 8 actually doubles the counter instead of incrementing it, so the larger the problem, the less additional work you have to do, so it's O(log(n))

*edit: Fragment 7 is O(n^5), not O(n^4) as I previously thought. This is because both j and k go from 1 to n * n. Sorry I didn't catch this earlier.

edited Oct 20 '08 at 18:22

answered Oct 19 '08 at 18:56

Kyle Cronin

77,653
43
148
164

oh okay, I see what you're saying! So for 5, the n * n means that the body of the inner loop will be executed order of N^2 times and compounding that with the order of N for the outer loop, overall it will be O(N^3). – 101010110101 Oct 19 '08 at 19:13
same idea for fragment 7. Man the fragment 8 went completely over my head. Sorry if this is asking too much, but I'm just curious what would the code for O(Nlog(N)) look like in case I ever run into it? – 101010110101 Oct 19 '08 at 19:16
1

For an O(n*log(n)) algorithm, imagine an outer loop that counts from 1 to n and an inner loop that goes from 1 to n by multiplying the counter by 2 each time. However, it's extremely unusual to encounter such algorithms. The most common O(n*log(n)) algorithms are the QuickSort and Merge Sort. – Kyle Cronin Oct 19 '08 at 19:22
okay, so basically if I were to put an outer (1 to n) loop around fragment 8, I would end up with an O(n*log(n)) algorithm because the outer O(n) loop and inner O(log(n)) would compound to form it. Thank you for all of your help! – 101010110101 Oct 19 '08 at 19:31
Yes. I'd code it up but comments don't display code well. – Kyle Cronin Oct 19 '08 at 19:38
1

Careful! Fragment 7 is O(n^5) not O(n^4) because the inner loop is also bounded by n^2. – Dave L. Oct 20 '08 at 18:19
Yikes, you're right Dave. I'll change my answer. – Kyle Cronin Oct 20 '08 at 18:21
As a little additional aside that you might already know, vpotok, fragment 8 runs about log base 2 n times for n items. But then again, no one really cares what base it's in, so we just say O(log n). – Andrew Szeto Jun 15 '09 at 15:58
@Andrew:What we does not care what base it's in? – Jichao Jan 04 '10 at 03:07

score 7 · Answer 2 · answered Oct 20 '08 at 18:18

7

Fragment 7 is O(n^5), not O(n^4) as the currently accepted comment claims. Otherwise, it's correct.

answered Oct 20 '08 at 18:18

Dave L.

43,907
11
63
62

score 2 · Answer 3 · answered Oct 19 '08 at 19:23

2

For case 8 try writing out the number of iterations for some values of N and see what the pattern looks like ... it isn't O(N)

answered Oct 19 '08 at 19:23

Rob Walker

46,588
15
99
136

score 0 · Answer 4 · edited May 23 '17 at 10:29

0

You appear to be on the right track. With regards to the N*N what effect do you think it would have? It is another factor of N so it would likely be a higher order.

Just a warning, I saw another post like this and it was extremely down voted. Be careful. Here is the post.

edited May 23 '17 at 10:29

Community

1
1

answered Oct 19 '08 at 18:56

smaclell

4,568
7
41
49

I actually upvoted the question, since he (1) obviously has made a serious attempt at solving the problems and (2) was honest about it being a homework. – JesperE Oct 19 '08 at 19:01
Oh I definitely agree, this is a solid attempt at the problem and a valid question. I just want to warn him in case others react poorly. Although in this case he should be fine. – smaclell Oct 19 '08 at 19:04

score 0 · Answer 5 · answered Nov 14 '11 at 12:42

You are on the right track, but here is a tip as to how things might get clearer along the way. Suppose you have some code :

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

Right, consider the fact that you have code at different levels. In this example, you can only see 3 levels so far :

The outer for-loop that goes from 0-n
Another for-loop that goes from 0-100
Some code inside, that is marked as ...

At no point in time should you try to calculate it all in 1 go. This is where most beginners make some kind of arithmetic error. Calculate it individually for each level and then multiply it all together.

Good luck!

Big O Notation Homework--Code Fragment Algorithm Analysis?

5 Answers5

Linked