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.