Self reference in Python - Time & Space Complexity

Time Complexity: Self reference

O(n)

Understanding Time Complexity

When a function calls itself, it uses self reference, also called recursion. Understanding how long this takes helps us know if the code will run fast or slow as input grows.

We want to find out how the number of steps grows when the function keeps calling itself.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def countdown(n):
    if n <= 0:
        return
    countdown(n - 1)

This function calls itself with a smaller number until it reaches zero, counting down step by step.

Identify Repeating Operations

• Primary operation: The function calls itself once each time with n reduced by 1.
• How many times: It repeats this call n times until it reaches zero.

How Execution Grows With Input

Each time the function calls itself, it does one step less until it stops.

Input Size (n)	Approx. Operations
10	10 calls
100	100 calls
1000	1000 calls

Pattern observation: The number of steps grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time it takes grows in a straight line with the input size.

Common Mistake

[X] Wrong: "Since the function calls itself, it must be very slow and take exponential time."

[OK] Correct: Here, the function calls itself only once each time, so the steps add up linearly, not multiply.

Interview Connect

Understanding how self reference affects time helps you explain recursive solutions clearly and confidently in real coding situations.

Self-Check

"What if the function called itself twice each time? How would the time complexity change?"