Choose the correct time complexity expression of the following pseudocode : START : count = 0 ;for ( i = 0 ; i <= n ; i++ )for ( j = 0 ; j <= n ; j = j+i ) count++
Question
Choose the correct time complexity expression of the following pseudocode : START : count = 0 ;for ( i = 0 ; i <= n ; i++ )for ( j = 0 ; j <= n ; j = j+i ) count++
Solution
The time complexity of the given pseudocode is O(n log n).
Here's why:
The outer loop runs n times. For each iteration of the outer loop, the inner loop runs approximately n/i times.
The total number of iterations is the sum of n/i for i from 1 to n. This is approximately n log n.
Therefore, the time complexity is O(n log n).
Similar Questions
What is time complexity of following code : int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j < i; j++) { count += 1; } }
What is the time complexity of the following code fragment?for(i=1; i<n; i= i*2) a[i]=0;
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;}
The time complexity of the following code snippet isc=0; while (n>=1) {for(i=1;i<=n;i++){ c++;}n=n/2;}
What will be the output of the following Pseudocode?Integer i, j, sum, nSet sum = 0 , n = 7Repeat for i = 1 to n Repeat for j = 1 to i - 1 sum = sum + j End loopEnd loopPrint sum
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.