determine the big o running time of the method

Question

Static void doIt (int n ) {
    int i;      // 1 operations
    int j; ← (2 x n)    // 1 operations
    while loop (j > 0) {    // n operations 
        I; ← n          // (n+1) operations
            while loop ( i>= 1) {   // (n*n) operations
                I;   ← i/2          // sqrt (n) operations
            }
            j; ← j -1           // (n+1) operations
     }
}

Static int myMethod (int n) {
    sum;  ←     // 1 operations
    for i ← 1 to n {    // (n operations)
        sum = sum + doIt(i);    // (n+1) operations
    }
    return 1;   // a 
}

Here is my solution for this pseudocode, but not sure if its correct

T(n) = 1 + 1 + n + (n+1) + (n*n) + sqrt(n) + 1 + n + (n+1) + a = n^2 + 5n + 5 + sqrt(n)  
big-o complexity = O(n^2)

Answer 1

I'll make a few assumptions. For instance, I'll assume tht int j; ← (2 x n) initializes j with 2*n. I wouldn't expect this semicolon there, but I can't continue otherwise.

With that in mind, your solution is incorrect.

while loop (j > 0) {    // n operations

Since j is initialized with 2n and decreases by one unit at a time, then this will perform 2n + 1 steps, not n. The decrement will perform 2n steps and the verification brings the +1 into the equation.

Then there's the inner loop:

while loop ( i>= 1) {   // (n*n) operations
    I;   ← i/2          // sqrt (n) operations
}

Assuming i and I are the same variable, then the assignment I <- I/2 will perform not sqrt(n), but up to log2(n) steps in each iteration of the outer loop. Therefore the while loop will run the product of the external loop by that value, that is, something upper-bounded by 2n × log2(n).

If you fix and sum everything, you'll see that doIt is O(n logn). The exact value involves the ceiling of log2(n) and a few constants.

The other function, myMethod, has a for loop:

sum = sum + doIt(i);    // (n+1) operations

This line will be run n times, not n + 1. If you don't need the exact function, that is, if you are only looking for the upper-bound in O notation, then this is O(n).

Since you are calling an O(n logn) algorithm O(n) times, this makes your entire algorithm O(n² logn).

Answer 2

Okay, so let's break down this code. We got a couple of functions doing their thing. First off, there's this doIt thing:

void doIt(int n) {
int i;          // 1 op
int j = 2 * n;   // 1 op
while (j > 0) {  // n loops
    i = n;       // (n+1) ops
    while (i >= 1) {  // n loops
        i = i / 2;    // sqrt(n) ops
    }
    j = j - 1;    // (n+1) ops
  }
}

Now, onto the main deal, the myMethod:

int myMethod(int n) {
    int sum = 0;      // 1 op
    for (int i = 1; i <= n; i++) {  // n loops
        sum = sum + doIt(i);        // (n+1) ops
    }
    return 1;          // 1 op
}

Now, let's add all those ops up and simplify the equation. We end up with:

T(n) = n^2 + 3n + 3 + n * sqrt(n)

Now, in the grand scheme of things, the big boss term here is n^2. So, in programmer lingo, we call it O(n^2)