Big O for while loops

Question

I had this question for my assignment the other day, but I was still not sure if I was 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 that nested for O (n ^ 2) loops, but I was not sure about the while loop. I assumed that all the code would be O (n ^ 3).

Answer 1

    int k=1;

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

It takes steps (n-1)/C: 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 O(n)(since it is Cconstant)

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

Start with a dummy variable u. Cycle

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

runs over MAXtime.

When you give a MAX = (n-1) / Cloop

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

And it works (n-1)/Conce.

u < (n-1)/C C*u < n-1 C*u + 1 < n,

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

, k = C * u + 1. ,

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

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

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

:

    int k=1;

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

(n-1)/C.

Answer 2

O(n/C)=O(n), , O(n^3) ( O(n))

Answer 3

(Sigma Notation):

a (a = 1, ).

Answer 4

Well, you will need to see how many times the body of the while loop starts for the given value of n and C. For example, n is 10 and C is 3. The body will work 3 times: k = 1, k = 4, k = 7. If n = 100 and C = 2, the body will work 50 times: k = 1,3,5,7,9, ..., 91,93,95,97,99. It is a matter of counting from C to n. You should be able to calculate Big-O complexity from this tooltip.