Big O for while loops

Question

I had this question for my assignment the other day, but I was still unsure if I'm right.

for(int i =1; i <n; i++)   //n is some size
{             
    for(j=1; j<i; j++)
    {
        int k=1;

        while (k<n)
        {
           k=k+C;   //where C is a constant and >=2
        }
    }
}

I know the nested for loops is O(n^2) but I wasn't sure with the while loop. I assumed that the whole code will be O(n^3).

Answer 1

The inner loop is literally O(n/C)=O(n), so yes, overall it's O(n^3) (the second loop has an upper bound of O(n))

Answer 2

    int k=1;

    while (k<n){
       k=k+C                    //where C is a constant and >=2
    }

This will take (n-1)/C steps: write u = (k-1)/C. Then, k = Cu + 1 and the statement becomes

u=0;
while(u < (n-1)/C) {
    u=u+1
}

Hence the while loop is O(n) (since C is constant)

EDIT: let me try to explain it the other way around.

Start with a dummy variable u. The loop

u=0;
while(u < MAX) {
    u = u+1
}

runs MAX times.

When you let MAX = (n-1) / C, the loop is

u=0;
while(u < (n-1)/C) {
    u=u+1
}

And that runs (n-1)/C times.

Now, the check u < (n-1)/C is equivalent to C*u < n-1 or C*u + 1 < n, so the loop is equivalent to

u=0;
while(C*u + 1 < n) {
    u=u+1
}

Now, suppose that we rewrote this loop in terms of a variable k = C * u + 1. Then,

u=0;
k=1; // C * 0 + 1 = 1

The loop looks like

while(C*u + 1 < n) {
while(k < n) {

and the inner condition is

    u=u+1
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 

Putting it all together:

    int k=1;

    while (k<n){
       k=k+C
    }

takes (n-1)/C steps.