Identify and state the running time using Big-O

Question

For each of the following algorithms, identify and state the running time using Big-O.

//i for (int i = 0; Math.sqrt(i) < n; i++)
cout << i << endl;

//ii for (int i = 0; i < n; i++){
cout << i << endl;
int k = n;
    while (k > 0)
    {
        k /= 2;
        cout << k << endl;
    } // while
}

//iii
int k = 1;
for (int i = 0; i < n; i++)
    k = k * 2;
for (int j = 0; j < k; j++)
    cout << j << endl;

I've calculate the loop times for the first question using n=1 and n=2. The loop in i will run n^2-1 times. Please help and guide me to identify the Big-O notation.

Answer 1

(i) for (int i = 0; Math.sqrt(i) < n; i++)
cout << i << endl;

The loop will run until squareRoot(i) < N , or until i < N^2. Thus the running time will be O(N^2), ie. quadratic.

(ii) for (int i = 0; i < n; i++){
        cout << i << endl;
        int k = n;
        while (k > 0)
        {
            k /= 2;
            cout << k << endl;
        } // while
      }

The outer loop will run for N iterations. The inner loop will run for logN iterations(because the inner loop will run for k=N, N/2, N/(2^2), N/(2^3), ...logN times). Thus the running time will be O(N logN), ie. linearithmic.

(iii)
int k = 1;
for (int i = 0; i < n; i++)
    k = k * 2;
for (int j = 0; j < k; j++)
    cout << j << endl;

The value of k after the execution of the first loop will be 2^n as k is multiplied by 2 n times. The second loop runs k times. Thus it will run for 2^n iterations. Running time is O(2^N), ie. exponential.