Kadane's Algorithm Maximum Subarray in DSA C - Time & Space Complexity

Time Complexity: Kadane's Algorithm Maximum Subarray

O(n)

Understanding Time Complexity

We want to understand how the time taken by Kadane's Algorithm changes as the input array grows.

Specifically, how many steps does it take to find the maximum sum of a continuous subarray?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int maxSubArray(int* nums, int numsSize) {
    int maxSoFar = nums[0];
    int currentMax = nums[0];
    for (int i = 1; i < numsSize; i++) {
        currentMax = (nums[i] > currentMax + nums[i]) ? nums[i] : currentMax + nums[i];
        maxSoFar = (maxSoFar > currentMax) ? maxSoFar : currentMax;
    }
    return maxSoFar;
}
    

This code finds the largest sum of any continuous subarray within the input array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single for-loop that goes through each element once.
• How many times: Exactly once for each element in the array, so n times.

How Execution Grows With Input

As the array size grows, the number of steps grows directly with it.

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 input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the size of the input array.

Common Mistake

[X] Wrong: "Kadane's Algorithm checks all subarrays, so it must be O(n²) or worse."

[OK] Correct: Kadane's cleverly keeps track of sums as it goes, so it only needs one pass through the array, not checking every subarray separately.

Interview Connect

Understanding Kadane's Algorithm time complexity shows you can spot efficient solutions that avoid unnecessary work, a key skill in coding interviews.

Self-Check

"What if we changed the algorithm to check every possible subarray sum by nested loops? How would the time complexity change?"