1.
What is the space complexity of Kadane's algorithm?
A
O(1)
B
O(n)
C
O(n^{2})
D
None of the mentioned
Answer and explanation
Correct Answer: A — O(1)
Kadane's algorithm uses a constant space. So, the space complexity is O(1).
ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
6 practice sets · Page 1 of 1
What is the space complexity of Kadane's algorithm?
O(1)
O(n)
O(n^{2})
None of the mentioned
Kadane's algorithm uses a constant space. So, the space complexity is O(1).
What is the time complexity of Kadane's algorithm?
O(1)
O(n)
O(n^{2})
O(5)
The time complexity of Kadane's algorithm is O(n) because there is only one for loop which scans the entire array exactly once.
For which of the following inputs would Kadane's algorithm produce a WRONG output?
{1,0,-1}
{-1,-2,-3}
{1,2,3}
{0,0,0}
Kadane's algorithm doesn't work for all negative numbers. So, the answer is {-1,-2,-3}.
For which of the following inputs would Kadane's algorithm produce the INCORRECT output?
{0,1,2,3}
{-1,0,1}
{-1,-2,-3,0}
{-4,-3,-2,-1}
Kadane's algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane's algorithm won't work.
Kadane's algorithm uses which of the following techniques?
Divide and conquer
Dynamic programming
Recursion
Greedy algorithm
Kadane's algorithm uses dynamic programming.
Kadane's algorithm is used to find ____________
Longest increasing subsequence
Longest palindrome subsequence
Maximum sub-array sum
Longest decreasing subsequence
Kadane's algorithm is used to find the maximum sub-array sum for a given array.