Knowee
Questions
Features
Study Tools

What is the time complexity of the following code :int i, j, k = 0;for (i = n/2; i <= n; i++) { for (j = 2; j <= n; j = j * 2) { k = k + n/2; }}

Question

What is the time complexity of the following code :

int i, j, k = 0;
for (i = n/2; i &lt;= n; i++) {
    for (j = 2; j &lt;= n; j = j * 2) {
        k = k + n/2;
    }
}
🧐 Not the exact question you are looking for?Go ask a question

Solution

The time complexity of the given code can be calculated as follows:

  1. The outer loop runs from n/2 to n. So, the time complexity of the outer loop is O(n).

  2. The inner loop runs from 2 to n with an increment of j = j * 2. This is a geometric progression, and the time complexity of this loop is O(log n).

  3. The statement inside the inner loop has a constant time complexity of O(1).

So, the total time complexity of the code is the product of the time complexities of these three parts. Therefore, the time complexity of the code is O(n log n).

This problem has been solved

Similar Questions

What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2)          a[i]=0; Group of answer choicesO(n/2)O(n^(1/2))O(n^2)O(log n)

The time complexity of the  following code snippet isc=0; while (n>=1) {for(i=1;i<=n;i++){ c++;}n=n/2;}

What is the running time of the following code?(i.e., O(?))Sum = 0;for (i=0; i<n; i++){for (j=0; j < i; j++)++sum;}

What is the time complexity of this function / algorithm?void f(int n){ printf("n = %d\n", n);}

What is the time complexity of accessing the nth element on an unsorted array?O(n!)O(2^n)O(1)O(n)O(nlog(n))O(n^2)O(log(n))

1/3

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.