How to answer these Big-O homework challenges?

Question

I am trying to see if I have these Big O questions right:

Determine the Big-O of the following:

a.    for (i = 0; i < N; i++){
         sequence of statements
    }
  for (j = 0; j < 1000000000*M; j++){
      sequence of statements
     }

This is O(NM) correct?

b.    for (i = 0; i < N; i++) {
          for (j = 0; j < i; j++) {
              sequence of statements
          }
     }
     for (k = 0; k < N; k++) {
        sequence of statements
     }

Is this O(n^4)?

c.    for (i = 0; i < N; i++) {
          for (j = i; j < i*i; j++) {
             sequence of statements
          }

I'm kinda stuck on this one....O(N^5)? or O(N^4) ?

@tanaydin, you're mistaken. "Questions asking for homework help must include a summary of the work you've done so far to solve the problem, and a description of the difficulty you are having solving it." (from http://stackoverflow.com/help/on-topic). So it would be better if the OP explained how he arrived at his answers, but homework itself is ok. — Erick G. Hagstrom, Jul 26 '15 at 20:34
@ErickG.Hagstrom - Yes, the real problem with this question is that OP has not shown any work. It's not clear what OP wants. (The answers to (a) and (b) are "no", "no", and "yes, one of those", but I suspect that those answers are not what OP wants. It's unclear to me just what OP _does_ want; is it correct answers or method for finding the answers, or both together?) — Ted Hopp, Jul 26 '15 at 20:58
Quite true, @TedHopp. (Though I believe the answer to c) to be "neither".) — Erick G. Hagstrom, Jul 26 '15 at 21:21

Am_I_Helpful · Answer 1 · 2015-08-24T10:37:49.773

2

a) No, first one is incorrect because both the for-loops are independent. The first for loop iterates for N times, whereas the second for-loop iterates for 1000000000*M times.

If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1 + f2 = O(|g1| + |g2|).

Check this Wikipedia link on Big O notation to know why the above.

So, overall time complexity = O(|N| + |M|).

b) The nested loop's time complexity comes out to be 1 + 2 + ... + N = N * (N+1)/2 = O(N²).

And, k-variable guided loop's complexity is O(N).

So, overall time complexity in this case is O(N²).

c) The 3rd case is somewhat complex.

When N = 2, the total iteration of both-loops = 0.

When N = 3, the total iteration of both-loops = 2.

When N = 4, the total iteration of both-loops = 2 + 6 = 8.

When N = 5, the total iteration of both-loops = 2 + 8 + 12 = 22.

...

When N = N(equals), the total iteration of both-loops = 2 + 8 + 22 + ... + (N-1)*(N-2) =

So, the total complexity

= 2 + 8 + 22 + ... + (N^2 - 3*N + 2)   
= 1/3 * (N-2) * (N-1) * N

Check this link to know how it was derived

= O(N^3).

So, overall time complexity = O(N³).

edited Aug 24 '15 at 10:37

answered Jul 26 '15 at 20:23

Am_I_Helpful

18,735
7
49
73

Good on a) and b). What about c)? Looks like O(N^3) to me. – Erick G. Hagstrom Jul 26 '15 at 20:31
@ErickG.Hagstrom-Didn't look. Seems OP edited the question after I've written the answer. Thanks, editing now... – Am_I_Helpful Jul 26 '15 at 20:33
1

@ErickG.Hagstrom-Yes, that is O(N^3). Please see my edit to the answer. – Am_I_Helpful Jul 26 '15 at 21:18
1

For part (c), it's not hard to derive that the overall number of operations is the sum of (i^2 - i) from 0 to N-1. The formula for [square pyramidal numbers](https://en.wikipedia.org/wiki/Square_pyramidal_number) comes in useful here. – Ted Hopp Jul 26 '15 at 21:24
@TedHopp-Actually, I did the same here. I just used wolfram alpha to give me the exact sum for `(i^2-i) for i-0 to (N-1)`. Acted somewhat lazy by not calculating it myself. :) – Am_I_Helpful Jul 26 '15 at 21:26
The WolframAlpha result is exact, so that's nice to use. I think OP would benefit greatly by learning how, when doing O() calculations, to throw out lower-order terms and recognize that the WolframAlpha result (or the Wikipedia one) is just O(N^3) without worrying about the lower-order terms. (That is, as far as O() calculations are concerned, summing (i^2 - i) is no different than summing i^2.) – Ted Hopp Jul 26 '15 at 21:33
1

I'd say O(max(M,N)) for the first part. – pjs Jul 26 '15 at 23:42
@pjs-No, you are incorrect in claiming the same. As the loops are independently guided by 2 variables, so the complexity would be `O(|M| + |N|)`. Please check my edit made and link to the Wikipedia. BTW, thanks for drawing my attention there, I missed the simplification there. Thanks... – Am_I_Helpful Jul 27 '15 at 05:13

How to answer these Big-O homework challenges?

1 Answers1