CODEWITHSUNDEEP
javaalgorithmbig-o
Javaturtle
Javaturtle

Reputation: 329

Worst Case Big O with Java Algorithms

1.

for(i = 0; i < 3; i++){
    for(j = 0; j < 10; j++){
        print i+j;
    }
}

I would assume Big O would be 30 since the most amount of times would be 3*10.

2.

for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
        print i+j;
    }
}

Would be O be n*m?

3.

for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
        for(int k = 1; k < 1000; k *= 2){
            print i+j+k;
        }
    }
}

n * m * log base 2 (1000) The Big O is in nlog(n) time

4.

for(i = 0; i < n - 10; i++){
    for(j = 0; j < m/2; j++){
        print i+j;
    }
}

5.

for(i = 0; i < n; i++){
   print i;
}
//n and m are some integers
for(j = 1; j < m; j *= 2){
   print j;
}

Can someone give me a hand with this if you know Big O. I am looking at these and at a loss. I hope I am posting this in the right location, I find these problems difficult. I appreciate any help.

Upvotes: 2

Views: 99

Answers (2)

Nick Zuber
Nick Zuber

Reputation: 5637

I think it's important just to point out that Big O notation is all about functions that, given an arbitrary constant, will be considered upper bounds at some point.

  1. O(1)

    This is because each loop iterates in a constant amount of time. We would refer to this as O(1) instead of O(30) because the function which is the upper bound is 1 with an arbitrary constant >=30.

  2. O(n*m)

    Simply because we have to loop through m iterations n times.

  3. O(n*m)

    This is the same as the previous one, only we're throwing in another loop in the middle. Now you can notice that this loop, similar to the first problem, is just a constant time. Therefore, you don't even need to really spend time figuring out how often it loops since it will always be constant - it is O(1) and would be interpreted as O(n*m*1) which we can simply call O(n*m)

  4. O(n*m)

    For the outer loop, don't get caught up on the .. - 10 and realize that we can just say that loop runs in O(n). We can ignore that .. - 10 for the same reason we ignored the exact values in the first problem; constants don't really matter. This same principle applies for the m/2 because you can think of m just being manipulated by a constant of 1/2. So we can just call this O(n*m).

  5. T(n) = O(n) + O(lg m) => O(n + lg m)

    So there are two components we have to look at here; the first loop and the second loop. The first loop is clearly O(n), so that's no problem. Now the second loop is a little tricky. Basically, you can notice that the iterator j is growing exponentially (notably power of 2's), therefore that loop will be running the inverse of exponentially (logarithmic). So this function runs in O(n + lg m).

Upvotes: 4

Amadan
Amadan

Reputation: 198294

Any constant factor can be ignored. O(30) is equal to O(1), which is what one would typically say for 1).

2) Just so.

3) in O(n*m*log_2(1000)), log_2(1000) is constant, so it's O(n*m).

4) O(n-10) is same as O(n). O(m/2) is same as O(m). Thus, O(n*m) again.

5) Trivially O(n).

6) O(log_2(m)).

Upvotes: 1

Related Questions