Time Complexity of Python Loops – GATE CSE 2026

Time Complexity of Python Loops – GATE CSE Complete Guide

Time Complexity is the most scoring topic for GATE CSE. 4-5 marks every year. Let’s understand in simple Hinglish.

What is Time Complexity?

Time Complexity tells how time increases when input size (n) increases. We use Big O notation.

Common Time Complexities for GATE

1. O(1) – Constant Time

a = 10
print(a)
# Always same time - O(1)

2. O(n) – Linear Time – Single Loop

for i in range(n):
    print(i)
# Loop runs n times - O(n)

3. O(n^2) – Quadratic Time – Nested Loop

for i in range(n):
    for j in range(n):
        print(i,j)
# n * n = O(n^2) - Very important for GATE

4. O(log n) – Logarithmic Time

while n > 0:
    n = n // 2
# n becomes half every time - O(log n)

GATE PYQ on Time Complexity

Q1. GATE CSE 2022

for i in range(n):
    for j in range(i):
        print("GATE")

Ans: 0+1+2+…+n-1 = n(n-1)/2 = O(n^2)

Q2. GATE CSE 2021

def fun(n):
    if n <= 1:
        return 1
    return fun(n-1) + fun(n-1)

Ans: T(n) = 2T(n-1) = O(2^n) – Exponential

Q3. GATE Favorite – Master Theorem

Q: T(n) = 2T(n/2) + n
Ans: O(n log n) – Merge Sort complexity

Q4. While Loop Complexity

i = 1
while i < n:
    i = i * 2

Ans: O(log n) because i doubles each time.

Quick Revision Table for GATE

Code Type	Complexity	GATE Example
Single loop n times	O(n)	Linear Search
Two nested loops	O(n^2)	Bubble Sort
Dividing by 2	O(log n)	Binary Search
Recursion T(n)=2T(n/2)+n	O(n log n)	Merge Sort

Conclusion

Remember Trick: Single loop O(n), Nested O(n^2), Divide by 2 O(log n). This topic will give 5 marks in GATE 2026.

Next Post: Python Functions and Scope GATE.