Asymptotic-Complexity
October 26, 2023Asymptotic-Complexity
October 26, 2023Asymptotic-Complexity
| Question 24 |
What is the running time of the following function(specified as a function of the input value)?
void Function(int n)
{
int i=1;
int s=1;
while(s<=n)
{
i++;
s=s+i;
}
}
void Function(int n)
{
int i=1;
int s=1;
while(s<=n)
{
i++;
s=s+i;
}
}
| O(n) | |
| O(n 2 ) | |
| O(1) | |
| O(√n) |
Question 24 Explanation:
S= 1, 3, 6, 10, 15 21….(>n) stopping condition.
i= 1, 2, 3, 4, 5, 6…..
Here, ‘S’ is nothing but sum of ‘n’ natural numbers
Assume the n=21, then corresponding k value 6. “k^2” is nothing but 36 which is greater than “n”
For any given K value , the S value is k(k+1)/2, So, 6(6+1)/2=21
the loop will terminate whenever k(k+1)/2 >n
k=O(√n)
i= 1, 2, 3, 4, 5, 6…..
Here, ‘S’ is nothing but sum of ‘n’ natural numbers
Assume the n=21, then corresponding k value 6. “k^2” is nothing but 36 which is greater than “n”
For any given K value , the S value is k(k+1)/2, So, 6(6+1)/2=21
the loop will terminate whenever k(k+1)/2 >n
k=O(√n)
Correct Answer: D
Question 24 Explanation:
S= 1, 3, 6, 10, 15 21….(>n) stopping condition.
i= 1, 2, 3, 4, 5, 6…..
Here, ‘S’ is nothing but sum of ‘n’ natural numbers
Assume the n=21, then corresponding k value 6. “k^2” is nothing but 36 which is greater than “n”
For any given K value , the S value is k(k+1)/2, So, 6(6+1)/2=21
the loop will terminate whenever k(k+1)/2 >n
k=O(√n)
i= 1, 2, 3, 4, 5, 6…..
Here, ‘S’ is nothing but sum of ‘n’ natural numbers
Assume the n=21, then corresponding k value 6. “k^2” is nothing but 36 which is greater than “n”
For any given K value , the S value is k(k+1)/2, So, 6(6+1)/2=21
the loop will terminate whenever k(k+1)/2 >n
k=O(√n)
Subscribe
Login
0 Comments