CODEWITHSUNDEEP
algorithmbig-otime-complexitypseudocode
veeyikpong
veeyikpong

Reputation: 857

Identify and state the running time using Big-O

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.

Upvotes: 2

Views: 310

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Using Sigma Notation, you can formally obtain the following results:

(i)

enter image description here

enter image description here

(ii)

enter image description here

(iii)

enter image description here

Upvotes: 0

Anycorn
Anycorn

Reputation: 51445

Couple hints may allow you to solve most of running time complexity problems in CS tests/homeworks.

  • If something decrease by a factor of 2 on each iteration, that's a log(N). In your second case the inner loop index is halved each time.

  • Geometric series, a r^0 + a r^1 + a r^2 ... = a (r^n - 1) / (r - 1).

    Write out third problem: 2 + 4 + 8 + 16 ... = 2^1 + 2^2 + 2^3 + 2^4 + ... and use the closed form formula.

Generally it helps to look for log2 and to write few terms to see if there is a repeatable pattern.

Other common questions require you to know factorials and its approximation (Sterling's approximation)

Upvotes: 0

turingcomplete
turingcomplete

Reputation: 2188

  • For the first question, you will have to loop until Math.sqrt(i) >= n, that means that you will stop when i >= n*n, thus the first program runs in O(n^2).

  • For the second question, the outer loop will execute n times, and the inner loop keeps repeatedly halving k (which is initially equal to n). So the inner loop executes log n times, thus the total time complexity is O(n log n).

  • For the third question, the first loop executes n times, and on each iteration you double the value of k which is initially 1. After the loop terminates, you will have k = 2^n, and the second loop executes k times, so the total complexity will be O(2^n)

Upvotes: 1

Nikunj Banka
Nikunj Banka

Reputation: 11365

(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.

Upvotes: 2

Related Questions