October 26, 2023
October 26, 2023
October 26, 2023
###### Asymptotic-Complexity
October 26, 2023
 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;
}
}
 A O(n) B O(n​ 2​ ) C O(1) D 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)
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)