Time Complexity: Kadane's Algorithm Maximum Subarray
O(n)
0
0
Kadane's Algorithm Maximum Subarray in DSA Python - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time needed to find the maximum sum of a continuous subarray changes as the input size grows.
How does the number of steps grow when the array gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
def max_subarray(arr):
max_ending_here = max_so_far = arr[0]
for x in arr[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
This code finds the largest sum of any continuous part of the array using Kadane's Algorithm.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: A single loop that goes through each element of the array once.
- How many times: Exactly once for each element, so n times if the array has n elements.
How Execution Grows With Input
As the array gets bigger, the number of steps grows directly with the number of elements.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 steps |
| 100 | About 100 steps |
| 1000 | About 1000 steps |
Pattern observation: The steps increase in a straight line as the input size grows.
Final Time Complexity
Time Complexity: O(n)
This means the time to find the maximum subarray grows directly with the size of the input array.
Common Mistake
[X] Wrong: "Since we check sums of many subarrays, the time must be quadratic O(nĀ²)."
[OK] Correct: Kadane's Algorithm cleverly keeps track of sums as it goes, so it only needs one pass through the array, not checking all subarrays separately.
Interview Connect
Understanding this linear time solution shows you can find efficient answers by smartly reusing information, a key skill in problem solving.
Self-Check
"What if we wanted to find the maximum subarray sum but also needed to return the start and end indexes? How would the time complexity change?"