Question

What is the running time of the best possible big o function of n?

1.

for(k = 1; k <= 999*n; k+=n) z++;

2.

for(i = 1; i*i*i <= n; i++) z++;

3.

for(i = 1; i*i <= n; i++){

for(j = 1; j*j <= n; j++){

z++;

}

}

Example:

for(i = 1; i <= n; i++)z++;

running time is O(n);

Answer 1

1.
for(k = 1; k <= 999*n; k+=n) z++;
Singe loop running for 1000n times.
So,
Time complexity = O(Largest term by removing constant) = O(n)

2.
for(i = 1; i*i*i <= n; i++) z++;
Singe loop running for cube root of n times.
So,
Time complexity = O(Largest term by removing constant) = O()

3.
for(i = 1; i*i <= n; i++){
    for(j = 1; j*j <= n; j++){
    z++;
    }
}
First loop running for sqrt(n) times.
Second loop running for sqrt(n) times.
Time complexity = O(Largest term by removing constant) =