Jump Game Problem in DSA C - Time & Space Complexity

Time Complexity: Jump Game Problem

O(n)

Understanding Time Complexity

We want to know how the time needed to solve the Jump Game grows as the input array gets bigger.

Specifically, how many steps does the algorithm take to decide if we can reach the end?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return false;
        if (i + nums[i] > maxReach) {
            maxReach = i + nums[i];
        }
    }
    return true;
}
    

This code checks if you can jump from the start to the end of the array, where each number tells the max jump length from that position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through the array once.
• How many times: The loop runs once for each element, so exactly n times where n is the array size.

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 checks and updates
100	About 100 checks and updates
1000	About 1000 checks and updates

Pattern observation: The work grows evenly as the input grows; doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if you can reach the end grows in a straight line with the size of the input array.

Common Mistake

[X] Wrong: "Because there is a loop inside a condition, the time complexity is more than linear."

[OK] Correct: The loop runs only once through the array, and the condition inside does not cause extra loops; it just checks a value, so the overall work is still linear.

Interview Connect

Understanding this linear time solution shows you can analyze and optimize problems efficiently, a key skill in real coding challenges.

Self-Check

"What if we used recursion to try every jump path? How would the time complexity change?"