Knowee
Questions
Features
Study Tools

Choose the correct time complexity expression of the following pseudocode : START : i , count = 0 ;while ( count < n )   i = i + 1 ;   count = count + i ;

Question

Choose the correct time complexity expression of the following pseudocode :

START : i , count = 0 ;
while ( count &lt; n )  
   i = i + 1 ;  
   count = count + i ;
🧐 Not the exact question you are looking for?Go ask a question

Solution

The time complexity of the given pseudocode is O(sqrt(n)).

Here's the step-by-step explanation:

  1. The loop runs until the variable 'count' is less than 'n'.
  2. In each iteration, 'i' is incremented by 1 and 'count' is incremented by 'i'.
  3. This means that 'count' increases by 1, then 2, then 3, and so on. This forms a series of 1 + 2 + 3 + ... + i.
  4. The sum of this series is (i*(i+1))/2. This sum is less than or equal to 'n'.
  5. Solving the equation (i*(i+1))/2 = n for 'i' gives us i = sqrt(2n) - 1/2 approximately.
  6. Therefore, the number of iterations, and hence the time complexity, is proportional to the square root of 'n'. Hence, the time complexity is O(sqrt(n)).

This problem has been solved

Similar Questions

Choose the correct time complexity expression of the following pseudocode : START : i , count = 0 ;while ( count < n )   i = i + 1 ;   count = count + i ;

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 will be the output of the following Pseudocode?int c = 0, d = 0 while ( d< 6 ) d=d+2 c=c+1 end while loop print c3564

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; }}

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.