Provide best-case and worst-case running time and space complexity analysis in B
ID: 3748566 • Letter: P
Question
Provide best-case and worst-case running time and space complexity analysis in Big-Oh notation for the following pow_2 method. For each case, provide an example input pair and brief explanation.
Big-O Notation
Example Input
Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity
public static long pow_2(long x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;
if (n % 2 == 0) {
return pow_2( x, n / 2 ) * pow_2( x, n / 2 );
} else {
return pow_2(x * x, n / 2) * x;
}
}
Big-O Notation
Example Input
Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity
Explanation / Answer
Best-Case Running Time - When n = 0 or n = 1 then whatever will be the value of x,the function will return value to the calling function in the 1st call only
Thus time = O(1)
Example - (x,n) = (13,0) or (13,1) Here x can be any value
Worst-Case Running Time - When n is any value other than 0 and 1 and n is a power of 2 as 2 function calls are made whenever n is even Note that when n is even Time required will be 2 * T(n/2) because 2 times function is called and in both calls value of n is reduced to half of the original.
That is T(n) = 2*T(n/2) Now if n/2 is even then -
T(n/2) = 4*T(n/4) Now if n/4 is even then -
This will continue
T(n/n) = n*T(n/n) = n*T(1) = n*1 = n (Since for n=1 const time is requires)
Thus time = O(n)
Example - (x,n) = (13,8) or (13,16) Here x can be any value and n is a power of 2
Best-Case Space Complexity - When n = 0 or n = 1 then whatever will be the value of x,the function will return value to the calling function in the 1st call only and hence no extra space will be needed
Thus space = O(1)
Example - (x,n) = (13,0) or (13,1) Here x can be any value
Worst-Case Space Complexity - When n is any value other than 0 and 1 When n is odd then only 1 function call is made in which value of n is reduced to half And if this pattern follows then log(n) space will be required
When n is even then 2 times function will be called and in both calls value of n is reduced to half But amongst this,2nd function call will be activated only on the termination of the 1st function call Thereby requiring log(n) space atmost
Thus space = O(log n)
Example - (x,n) = (13,8) or (13,15) Here x can be any value and n is anything other than 0 and 1
Hope i have answered your question satisfactorily.If you want more examples or a clearer explaination then tell me through comments Leave doubts in comment section if any.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.