How to count the number of operations in a loop and give a theta characterization

Question

I just want to make sure if I am doing this correct. I am trying to count the number of operations performed for the worst case scenario in java

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

Is the number of operations 2+3n or 3+3n?

I got the answer from counting int sum = 0 and int i = 0 for the "2" and i < n, i++, and sum++ as the "3n". Or is it a 3 rather than a 2 because I have to count i < n before going through the loop?

But either way, is the theta characterization going to be Θ(n)?

Now what if there is a nested for loop like this:

int sum = 0;
    for (int i = 0; i < n; i++ )
        for (int a = 0; a < i; a++)
            sum++;

would it be 3+n*(6a+2) = 6na+2n+3? with Θ(n^2)?

if i change the inner for loop from a < i to a < i*i, would the equation still hold as above or change?

Answer 1

It'll be 3+3n, because the comparison runs for each value of i from 0 to n inclusive. I'd says that's O(n).

Answer 2

I would it count as 3+3n, because when n = 0 then you execute the following 3 commands:

int sum = 0;
int i = 0;
i < n

Now when n != 0 then you execute the declarations once (2) and for each execution of the loop each command once (3n) and the final comparison (which fails; 1). That makes 3+3n.

And yes, that would be Θ(n) (and O(n) and o(n)).

Answer 3

Yes, exactly. Look here for a mathematical definition.

It doesn't matter if you use 2+3n or 3+3n. You have lim_n->infty ( (3+3n)/n ) = 3 (both lim sup and lim inf are the same here). Because of that limites (which is greater 0 and not infinity), you know that is Big Theta n.

In your second example, you cannot use the inner-loop variables (a or i). The amount of sum++ operations:

• When i == 0: zero sum++s are executed.
• When i == 1: exactly one sum++ get's executed (when a==0).
• When i == 2: 2 sum++s (a==0 and a==1)
• When i == 3: 3 sum++s (a==0, a==1 and a==2)
• ...
• When i == n-1: n-1 sum++s (a==0, a==1, ... and finally a==n-1)

That are all sum++s in your code. So let's sum them together:

0 + 1 + 2 + ... + n - 1

That is the same as (n-1)(n-2)/2.

I.e. we have Θ(n^2 + n). The same thing for a++ and a < i (well, one more to be exact but that doesn't matter). The amount of i++ ops is just n. So you end up with Θ(n^2).

Answer 4

Maybe it's easier to count the number of executions of each statement if there's only one per line:

int sum = 0;     // 1 time
int i = 0;       // 1 time
while (i < n) {  // n+1 times
  sum++;         // n times
  i++;           // n times
}

Hence, T(n) = 3*n+3 = Θ(n).

int sum = 0;       // 1 time
int i = 0;         // 1 time
while (i < n) {    // n+1 times
  int a = 0;       // n times
  while (a < i) {  // 1 + 2 + ... + n = n*(n+1)/2 times
    sum++;         // 0 + 1 + ... + n-1 = n*(n-1)/2 times
    a++;           // 0 + 1 + ... + n-1 = n*(n-1)/2 times
  }
  i++;             // n times
}

Hence, T(n) = 3*n+3 + n*(n-1) + n*(n+1)/2 = Θ(n^2).