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
Correct Answer: A — O(1)
Explanation:
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)
Correct Answer: B — O(n)
Explanation:
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}
Correct Answer: B — {-1,-2,-3}
Explanation:
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}
Correct Answer: D — {-4,-3,-2,-1}
Explanation:
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
Correct Answer: B — Dynamic programming
Explanation:
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
Correct Answer: C — Maximum sub-array sum
Explanation:
Kadane's algorithm is used to find the maximum sub-array sum for a given array.
