Big O Notation Homework--Code Fragment Algorithm Analysis? [closed]

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

Answer 1

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.

Answer 2

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

Answer 3

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)

Answer 4

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.

Answer 5

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 :

1. The outer for-loop that goes from 0-n
2. Another for-loop that goes from 0-100
3. 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!