How Python executes code - Performance & Efficiency

Time Complexity: How Python executes code

O(n)

Understanding Time Complexity

We want to understand how Python runs code and how the time it takes changes as the code gets bigger or more complex.

Our question: How does the work Python does grow when the input or code size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i in range(n):
    print(i)

sum = 0
for j in range(n):
    sum += j
print(sum)
    

This code prints numbers from 0 to n-1, then sums numbers from 0 to n-1 and prints the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two separate loops each running from 0 to n-1.
• How many times: Each loop runs n times, so total loops run about 2n times.

How Execution Grows With Input

As n grows, the total work grows roughly twice as fast because of two loops.

Input Size (n)	Approx. Operations
10	About 20 operations (2 loops x 10 each)
100	About 200 operations
1000	About 2000 operations

Pattern observation: The work grows in a straight line as n grows, doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time Python takes grows directly in proportion to the size of the input n.

Common Mistake

[X] Wrong: "Two loops mean the time complexity is O(n²)."

[OK] Correct: The loops run one after another, not inside each other, so their times add up, not multiply.

Interview Connect

Understanding how Python runs code and how time grows with input helps you explain your solutions clearly and confidently in interviews.

Self-Check

"What if the second loop was inside the first loop? How would the time complexity change?"