Analysing Loops and Nested Loops
Calculate time complexity for single loops, nested loops, and loops with shrinking ranges such as binary search or triangle iterations.
Analysing Loops and Nested Loops is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Single Loop: O(n)
The simplest loop runs its body n times, so it is O(n). A bigger step changes the count but not the class. Always start by counting how often the body runs. See the code.
# O(n): body runs n times
def count_ops_linear(n):
ops = 0
for i in range(n):
ops += 1 # constant work
return ops
print(count_ops_linear(100)) # 100
# Still O(n): step=2 halves count but same class
def count_ops_half(n):
ops = 0
for i in range(0, n, 2):
ops += 1
return ops
print(count_ops_half(100)) # 50 => O(n)Nested Loops: O(n²) and Beyond
Two loops nested, each n times, give n x n = O(n^2); three give O(n^3). But if the inner loop runs a fixed number of times, the whole thing stays linear.
def count_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(n): # n iterations each
ops += 1
return ops
print(count_pairs(10)) # 100 = 10^2
print(count_pairs(100)) # 10000 = 100^2
# Doubling n quadruples ops: classic O(n^2)Triangular Loop: O(n²/2) = O(n²)
When the inner loop starts at i+1, iterations form a triangle: n(n-1)/2, which is still O(n^2) after dropping the half. All-unique-pairs problems look like this.
def count_unique_pairs(n):
ops = 0
for i in range(n): # n iterations
for j in range(i+1, n): # n-1, n-2, ..., 0
ops += 1
return ops
print(count_unique_pairs(10)) # 45 = 10*9/2
print(count_unique_pairs(100)) # 4950
# Still O(n^2) -- constant factor 1/2 droppedShrinking Range Loop: O(log n)
When the loop variable is halved each step, you get O(log n). The key question: does the range shrink multiplicatively (log n) or additively (n)? See the code.
def count_log_ops(n):
ops = 0
i = n
while i >= 1:
ops += 1
i //= 2 # halve each iteration
return ops
import math
for n in [8, 16, 64, 1024]:
ops = count_log_ops(n)
print(f'n={n}, ops={ops}, log2={int(math.log2(n))}')
# ops tracks log2(n) closelyNested Loop with Shrinking Inner: O(n log n)
An n-times outer loop with an O(log n) inner loop gives O(n log n) — the shape of merge sort. Spotting an O(log n) inner step is the key to analyzing sorts.
import math
def count_n_log_n(n):
ops = 0
for i in range(n): # n iterations
j = n
while j >= 1: # log n iterations
ops += 1
j //= 2
return ops
for n in [8, 32, 128]:
ops = count_n_log_n(n)
predicted = int(n * math.log2(n))
print(f'n={n}: actual={ops}, n*log2(n)~={predicted}')Dependent Inner Loops
When the inner loop's range depends on the outer index, count total iterations, not per-step. An inner loop running 0..i sums to n(n-1)/2 = O(n^2). See the code.
# Inner loop runs i times: total = 0+1+2+...+(n-1) = n(n-1)/2 => O(n^2)
def sum_inner_i(n):
ops = 0
for i in range(n):
for j in range(i): # runs 0,1,2,...,n-1 times
ops += 1
return ops
print(sum_inner_i(10)) # 45 = 10*9/2 => O(n^2)
# Inner loop runs n/i times (i doubles): sum ≈ n*log n => O(n log n)
def sum_inner_n_over_i(n):
ops = 0
i = 1
while i <= n:
for j in range(n // i):
ops += 1
i *= 2
return ops
print(sum_inner_n_over_i(64)) # ~ 64*6 = 384Bubble Sort Analysis Step by Step
Bubble sort compares n(n-1)/2 times, so O(n^2). Even with early exit, a reverse-sorted input still needs every comparison. Too slow for large inputs.
def bubble_sort(arr):
n = len(arr)
comparisons = 0
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # early exit if sorted
break
return comparisons
arr = list(range(10, 0, -1)) # worst case: reversed
ops = bubble_sort(arr)
print(f'Sorted: {arr}')
print(f'Comparisons: {ops}') # 45 = 10*9/2Loops Over Strings and Substrings
Watch out: Python slicing is O(k), not free, and string concat with + in a loop is O(n^2) because it copies each time. Use ''.join(parts) instead. See the code.
# O(n^2): string concat in loop
def build_bad(n):
s = ''
for i in range(n):
s += str(i) # copies s each time!
return s
# O(n): join is a single pass
def build_good(n):
parts = []
for i in range(n):
parts.append(str(i))
return ''.join(parts)
print(build_good(10)) # '0123456789'Multiple Input Parameters
With two inputs, complexity may use both: O(m + n) for separate work, O(m x n) for nested. Graphs often read as O(V + E). Name each variable clearly.
# O(m + n): two independent loops
def independent(m, n):
a = sum(range(m)) # O(m)
b = sum(range(n)) # O(n)
return a + b # total O(m + n)
# O(m * n): nested
def nested(m, n):
count = 0
for i in range(m): # O(m)
for j in range(n): # O(n) each
count += 1
return count # O(m * n)
print(independent(5, 10)) # 10 + 45 = 55
print(nested(5, 10)) # 50Loop-in-Loop vs Sequential Calls
A function call is not free — its inner loop counts too. Call an O(n) helper n times and you get O(n^2). Always look inside black-box calls when analyzing.
# Naive string matching: O(n*m)
def naive_search(text, pattern):
n, m = len(text), len(pattern)
matches = []
for i in range(n - m + 1): # O(n)
if text[i:i+m] == pattern: # O(m) comparison + O(m) slice
matches.append(i)
return matches
# Total: O(n*m)
print(naive_search('abcabcabc', 'abc')) # [0, 3, 6]Practical: Identify Complexity at a Glance
Build a habit: count loop nesting, check if the inner loop depends on the outer, and watch for hidden costs in function calls and slicing. The code is a puzzle to try.
# What is the complexity of this function?
def mystery(nums):
result = []
for i in range(len(nums)): # O(n)
for j in range(i, len(nums)): # O(n) worst
if sum(nums[i:j+1]) == 0: # O(n) slice + sum!
result.append((i, j))
return result
# Answer: O(n^3) -- three nested n-proportional ops
# Outer O(n) x inner O(n) x sum/slice O(n) = O(n^3)Quick Check
Quick check — see how well the loop-analysis tricks stuck. Trust your reasoning here. 💪
Lesson Recap
Recap: nested loops multiply and independent ones add, a halving inner loop gives O(n log n), and hidden costs inside calls and slicing must be counted too.
Frequently asked questions
Is the “Analysing Loops and Nested Loops” lesson free?
Yes — the full text of “Analysing Loops and Nested Loops” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Analysing Loops and Nested Loops”?
Calculate time complexity for single loops, nested loops, and loops with shrinking ranges such as binary search or triangle iterations. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Analysing Loops and Nested Loops” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Big-O Notation from Scratch
- Analysing Loops and Nested Loops
- Recursion and the Recursion Tree Method
- Space Complexity and Trade-offs