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?"

Practice

1. What does self represent inside a Python class method?

easy

A. A class method decorator

B. The current instance of the class

C. A global variable

D. A built-in Python keyword

Solution

1. Step 1: Understand the role of self in classes

   self is used to refer to the current object instance inside class methods.

2. Step 2: Differentiate from other options

   It is not a global variable, decorator, or keyword but a conventional name for the instance parameter.

3. Final Answer:

   The current instance of the class -> Option B

4. Quick Check:

   self = current object [OK]

Hint: Remember: self means 'this object' inside class methods [OK]

Common Mistakes:

• Thinking self is a keyword
• Confusing self with class itself
• Assuming self is optional

2. Which of the following is the correct way to define a method using self in a Python class?

easy

A. def method(self):

B. def method(this):

C. def method(cls):

D. def method():

Solution

1. Step 1: Recall method definition syntax in Python classes

   Instance methods must include self as the first parameter to access instance data.

2. Step 2: Check each option

   Only def method(self): correctly includes self as the first parameter.

3. Final Answer:

   def method(self): -> Option A

4. Quick Check:

   Method needs self parameter [OK]

Hint: Always put self as first parameter in instance methods [OK]

Common Mistakes:

• Omitting self parameter
• Using wrong parameter name like cls or this
• Confusing class and instance methods

3. What is the output of this code?

class Counter:
    def __init__(self):
        self.count = 0
    def increment(self):
        self.count += 1
        return self.count
c = Counter()
print(c.increment())
print(c.increment())

medium

A. 1 2

B. 0 1

C. 1 1

D. 2 3

Solution

1. Step 1: Understand the initial state and method behavior

   When Counter is created, count is 0. Each increment adds 1 and returns the new value.

2. Step 2: Trace the two calls to increment()

   First call: count goes 0 -> 1, returns 1. Second call: count goes 1 -> 2, returns 2.

3. Final Answer:

   1 2 -> Option A

4. Quick Check:

   Increment adds 1 each call [OK]

Hint: Track self.count changes step-by-step [OK]

Common Mistakes:

• Assuming count resets each call
• Confusing return values
• Ignoring self reference updates

4. Find the error in this class definition:

class Person:
    def __init__(name):
        self.name = name
p = Person('Alice')
print(p.name)

medium

A. Using self before assignment

B. Incorrect print statement

C. Missing self parameter in __init__

D. Class name should be lowercase

Solution

1. Step 1: Check method parameters

   The __init__ method must have self as the first parameter to refer to the instance.

2. Step 2: Identify the error

   Here, __init__ only has name, so self is missing, causing a runtime error.

3. Final Answer:

   Missing self parameter in __init__ -> Option C

4. Quick Check:

   __init__ needs self first [OK]

Hint: Always include self as first parameter in instance methods [OK]

Common Mistakes:

• Forgetting self in __init__
• Trying to use self without defining it
• Assuming self is automatic

5. You want to create a class Node for a linked list where each node refers to itself and the next node. Which is the correct way to set the next node using self reference?

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
    def set_next(self, next_node):
        ???

Choose the correct line to replace ???.

hard

A. next_node = self.next

B. next = self.next_node

C. self.next_node = next_node

D. self.next = next_node

Solution

1. Step 1: Understand attribute assignment with self

   To update the current object's next attribute, use self.next.

2. Step 2: Match the correct assignment

   Assigning self.next = next_node correctly sets the next node reference.

3. Final Answer:

   self.next = next_node -> Option D

4. Quick Check:

   Use self.attribute = value to update instance data [OK]

Hint: Use self.attribute to refer to current object's data [OK]

Common Mistakes:

• Assigning to local variable instead of self attribute
• Mixing attribute names
• Forgetting self in assignment