Here are some common Big O examples in Python, with short code snippets and explanations of time complexity of each of them. First we see the general examples then we go with some practice exercise with solutions.
Steps to Learn the Big O Examples in Python
- First we are go through the Common Big O classes 𝑂(1), 𝑂(log 𝑛), 𝑂(𝑛), 𝑂(𝑛 log 𝑛), and 𝑂(𝑛2) in simple code pattern
- Learn the Python Data Structures with quick overview
- Go Through the Practical Example with code snippets.
- See Some Interview Questions
1. Common Big O classes Examples in Python
1.1. Constant time — O(1)
Operations that take the same amount of time regardless of input size ie n.
def find_first_index(list1):
print(list1[0])
1.2. Linear time — 𝑂(𝑛)
The work grows proportionally with the input size, execution time scales one to one with input size.
def print_items(items):
for item in items:
print(item)
If there are n items, the loop runs n times.
Searching an unsorted Python list can take O(n) in the worst case.
1.3. Logarithmic - O(log n)
The algorithm repeatedly cuts the problem down, often by half with every iteration. It is highly efficient for large datasets.
A classic example is binary search:
def binary_search(arr, target):
left, right = 0, len(arr)
while left <= right:
mid = (left + right)
if arr[mid] == target:
return True
elif arr[mid] <target:
left = mid + 1
else:
right = mid - 1
return False
Each step eliminates about half of the remaining elements.
1.4. Linearithmic - O(n log n)
The Time of an alogorithm grows at a liner log arthmic rate with the size of input, n which means performace is impacted with the input size and lograthim of the input size. Common in efficient sorting algorithms.
items.sort()
Python's list.sort() / sorted() use
Timsort, whose worst-case time complexity is O(n log n).
Example:
numbers = [5, 2, 8, 1, >3]
numbers.sort()
1.5. Quadratic - O(n²)
Usually occurs when you have a loop inside another loop.
def print_pairs(items): for x in items: for y in items: print(x, y)
For n items:
-
Outer loop →
n -
Inner loop →
n -
Total →
n × n
A common example is a simple comparison of every pair.
1.6. Exponential - O(2ⁿ)
The amount of work doubles as n increases by one.
A classic example is the naive recursive Fibonacci implementation:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
This repeatedly calculates the same values. Using dynamic programming can reduce this dramatically.
The Time Complexities in python Summarized
O(1) — Constant time complexity: An algorithm exhibits constant time complexity when its execution duration remains unchanged irrespective of the input magnitude. Illustration: retrieving an element from an array.
O(log n) — Logarithmic time complexity: An algorithm demonstrates logarithmic time complexity when its execution duration increases logarithmically relative to the input magnitude. Illustration: binary search methodology.
O(n) — Linear time complexity: An algorithm exhibits linear time complexity when its execution duration increases proportionally with the input magnitude. Illustration: linear search methodology.
O(n log n) — Linearithmic time complexity: An algorithm demonstrates linearithmic time complexity when its execution duration increases at a linear-logarithmic proportion relative to the input magnitude. Illustration: merge sort algorithm.
O(n²) — Quadratic time complexity: An algorithm exhibits quadratic time complexity when its execution duration increases quadratically with the input magnitude. Illustration: bubble sort algorithm.
O(2n) — Exponential time complexity: An algorithm demonstrates exponential time complexity when its execution duration increases exponentially relative to the input magnitude. Illustration: naive recursive Fibonacci sequence implementation.
O(n!) — Factorial time complexity: An algorithm exhibits factorial time complexity when its execution duration increases at a factorial proportion with the input magnitude. Illustration: brute-force approach to the traveling salesman problem
Quick Summary Table Python examples
| Big O | Python example | Idea |
|---|---|---|
| O(1) |
items[0]
|
Constant |
| O(log n) | Binary search | Halves the problem |
| O(n) |
for x in items
|
Visit each item |
| O(n log n) |
items.sort()
|
Efficient sorting |
| O(n²) | Nested loops | Compare pairs |
| O(2ⁿ) | Naive Fibonacci | Repeated branching |
2. Common Python data structures
Now we are going to see common Python data structures (list,
dict, set, tuple)
Python Data Structures — Big O Cheat Sheet
| Operation | List | Tuple | Set | Dict |
|---|---|---|---|---|
| Access by index | O(1) | O(1) | — | — |
| Search (x in) | O(n) | O(n) | O(1) avg. | O(1) avg. |
| Append | O(1) amortized | — | O(1) avg. | O(1) avg. |
| Insert at beginning | O(n) | — | — | — |
| Insert at end | O(1) amortized | — | — | O(1) avg. |
| Delete by value | O(n) | — | O(1) avg. | O(1) avg. |
| Access by key | — | — | — | O(1) avg. |
| Sorting | O(n log n) | sorted() → O(n log n) |
2.1. Python List
A Pythonlist is essentially a dynamic array.
Access — O(1)
numbers = [10, 20, 30, 40, 50]
print(numbers[3])
Python can directly calculate where index 3 is located.
O(1)
Append — O(1) amortized
numbers.append(60)Usually, Python simply adds the element at the end.
O(1) amortized
"amortized"? Occasionally Python needs to allocate a larger block of memory and copy elements, which takes O(n), but over many appends the average cost is O(1).
Insert at beginning — O(n)
numbers.insert(0, 5)Existing elements have to be shifted:
[10, 20, 30, 40]
↓
[5, 10, 20, 30, 40](n)
if you frequently add/remove items from the beginning, consider collections.deque instead of a list.
Searching a List — O(n)
numbers = [10, 20, 30, 40, 50]
if 40 in numbers:
print("Found")
may need to check:
10 → 20 → 30 → 40Worst case:
10 → 20 → 30 → 40 → 50 → not foundSo searching a list is typically:
O(n)Dictionary — O(1) Average
Dictionaries use hash tables.
person = {
"name": "Alice",
"age": 25
}
print(person["name"])Finding "name" is typically:
O(1) average
This is why dictionaries are extremely useful for fast lookups.
Example
Instead of:
users = ["Alice", >"Bob", >"Charlie"]
if >"Charlie" >in users:
...
you could use:
users = >{
>"Alice": >101,
>"Bob": >102,
>"Charlie": >103
}
if >"Charlie" >in users:
...
The list lookup is O(n), while dictionary lookup is O(1) average.
Set — O(1) Average Lookup
Sets are also hash-table based.
numbers = {10, 20, 30, 40, 50}
if >30 >in numbers:
>print("Found")Average:
O(1)
makes sets particularly useful when you need to repeatedly ask:
"Have I seen this value before?"
Example
seen = >set()
for number in numbers:
>if number in seen:
>print("Duplicate!")
seen.add(number) Each lookup is approximately O(1), so the entire loop is approximately:
O(n)
Tuple
Tuples are similar to lists for indexing.
numbers = (10, 20, 30, 40)
print(numbers[2]) access:
O(1)
Tuples are immutable, so you cannot do:
numbers.append(50) ># ErrorSearching is still:
30 >in numbersWhat is the difference between list and tuple?
Ans
The List is changable, in which items can be added or remove but in the Tuple it can not be changed. If you want the items that you created can not be changed by anyone, than you can use tuple.
list1=[1,2,3]
list1[1]=1000
print(list1)
tup =(1,2,3)
# tup[1]=100 # it can not be changed.
Big O Patterns to Memorize
list[index] → O(1)
list.append(x) → O(1) amortized
list.pop() → O(1)
list.insert(0,x) → O(n)
list.pop(0) → O(n)
x in list → O(n)
x in set → O(1) average
dict[key] → O(1) average
for x in list → O(n)
nested loops → O(n²)
list.sort() → O(n log n)Practice exercises with solutions
Exercise 1
def ex1(lst):
return lst[0] + lst[-1]
Question: What is the time complexity of ex1 in terms of n = len(lst)?
Solution:
def ex1(lst):
return lst[0] + lst[-1]
Two list index operations: lst[0] and lst[-1].
Each index access is O(1).
Time complexity: O(1).
Exercise 2
def ex2(lst):
total = 0
for x in lst:
total += x
for x in lst:
total -= x
return total
Question: What is the time complexity of ex2?
Solution:
The function has two separate loops,
each iterating through the list once.
First loop: runs n times → O(n).
Second loop: runs n times → O(n).
Total: O(n) + O(n) = O(n).
Time complexity: O(n).
Exercise 3
def ex3(lst):
for i in range(len(lst)):
for j in range(i, len(lst)):
print(lst[i], lst[j])Question: What is the time complexity of ex3?
Solution:
The function has nested loops, where the inner loop runs from the current index of the outer loop to the end of the list. In the worst case, this results in approximately n² iterations.
Outer loop: i from 0 to n−1.
Inner loop: j from i to n−1 → about (n − i) iterations.
Total iterations ≈ n + (n−1) + … + 1 = n(n+1)/2 = O(n²)
Time complexity: O(n²).
Exercise 4
def ex4(n):
count = 0
while n > 1:
n = n // 2
count += 1
return count
Question: What is the time complexity of ex4 in terms of the input value n?
Solution:
The function divides n by 2 in each iteration until n becomes 1.
This results in approximately log₂(n) iterations.
Each iteration halves n.
Number of halvings until n becomes 1 is about log₂(n).
Time complexity: O(log n).
Exercise 5
def ex5(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
Question: What is the worst-case time complexity of ex5?
Solution:
In the worst case, the target is not found in the list, and the function must iterate through all elements. Worst-case time complexity: O(n).
Exercise 6
def ex6(lst):
d = {}
for x in lst:
d[x] = d.get(x, 0) + 1
return dQuestion: What is the time complexity of ex6? (Assume average-case dictionary operations.)
Solution:
The function iterates through the list once, and each dictionary operation (get and set) is O(1) on average.
Loop runs n times.
Each dict lookup/insert (d.get, d[...]) is O(1) on average.
Average-case time complexity: O(n).
Exercise 7
def ex7(lst):
result = []
for x in lst:
result.append(x * 2)
return result
Question: What are the time and space complexities of ex7?
Solution:
Solution: The function iterates through the list once, performing a constant-time operation for each element. Time complexity: O(n). The function creates a new list of the same size as the input list. Space complexity: O(n).
- Loop runs n times; each
appendis O(1) amortized. - Creates a new list of size n.
Time complexity: O(n).
Space complexity: O(n) extra space forresult.
Exercise 8
def ex8(lst):
total = 0
for x in lst:
for y in lst:
total += x * y
return total
Question: What is the time complexity of ex8?
Solution:
The function has nested loops, where the inner loop runs for each element of the list. In the worst case, this results in approximately n² iterations.
- Outer loop: n iterations.
- Inner loop: n iterations for each outer iteration.
- Total operations ≈ n × n = n².
Time complexity: O(n²).
Exercise 9
def example(arr):
arr.sort()
for x in arr:
print(x)
Question: What is the time complexity of mystery?
Solution:
Python's list.sort() uses Timsort, whose worst-case time complexity is: O(n log n), therafter loop is O(n) Therefore: O(n log n + n) The dominant term is n log n.
Time complexity:O(n log n)
Exercise 10
def example(arr):
arr.sort()
for x in arr:
print(x)
Question: What is the time complexity of mystery?
Solution:
Each call creates two more calls: T(n) = 2T(n-1) + O(1)This produces exponential growth O(2ⁿ)
Time complexity:O(2ⁿ)
Exercise 11
def mystery(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False
Question: What is the worst-case complexity?
Solution:
Worst case means no duplicate is found, so both loops run almost completely. n × n
Worst-case complexity Time complexity:O(n²)
20 Big-O Practice Questions in Python
Try to identify the time complexity of each snippet before checking the answer key.Assume n = len(arr) where applicable.
1. Easy
def example(n): for i in range(n): print(i) 2. Constant work
def
example(arr): print(arr[0]) print(arr[-1]) 3. Two loops
def example(n): for i in range(n):
print(i) for j in range(n): print(j) 4. Nested loops
def example(n): for i in range(n): for j
in range(n): print(i, j) 5. Different loop sizes
def example(n): for i in range(n): for j in
range(10): print(i, j) 6. Logarithmic
def example(n): i = 1 while i < n: print(i) i *=2 Your
7. Dividing
def example(n): while n > 1: n //= 2 Answer: O(?)
8. Nested with logarithm
def
example(n): for i in range(n): j = 1 while j < n: print(i, j) j *=2 Answer: O(?)
9. Triangular loop
def example(n): for i in range(n): for j in range(i): print(i, j) 10. Three nested loops
def example(n): for i in range(n): for j in range(n): for k in range(n): print(i, j, k) 11. List search
def contains(arr, target): for x in arr: if x == target: return True return False What is
the worst-case complexity? 12. Dictionary lookup
def find_user(users, name): return
users[name] Assume users is a Python dictionary. 13. Sorting + loop
def example(arr):
arr.sort() for x in arr: print(x) 14. Nested list membership
def example(arr, values):
for x in arr: if x in values: print(x) Assume values is a list. 15. Nested dictionary membership
def example(arr, values): for x in arr: if x in values: print(x) This time, assume values is a
set. 16. Recursive — one branch
def example(n): if n <= 1: return example(n - 1) Your
17. Recursive — two branches
def example(n): if n <= 1: return example(n - 1) example(n -
1) 18. Sneaky one
def example(n): i = 1 while i < n: for j in range(n): print(i,
j) i *=2 19. Very sneaky
def example(n): i = 1 while i < n: j=1 while j < n:
print(i, j) j *=2 i *=2 20. Interview challenge
def example(arr): n =
len(arr) for i in range(n): j = i while j < n: print(arr[i], arr[j]) j +=1 | # | Python code / question | Answer | Why? |
|---|---|---|---|
| 1 | for i in range(n): | O(n) | Loop runs n times |
| 2 | print(arr[0])<br>print(arr[-1]) | O(1) | Fixed number of operations |
| 3 | Two separate for loops of n | O(n) | n + n = 2n → O(n) |
| 4 | for i in range(n)<br>inside for j in range(n) | O(n²) | n × n |
| 5 | for i in range(n)<br>inside for j in range(10) | O(n) | n × 10 = 10n → O(n) |
| 6 | i = 1 → i *= 2 | O(log n) | Value doubles each time |
| 7 | n //= 2 repeatedly | O(log n) | Problem size halves each time |
| 8 | n loop + inner loop doubling j | O(n log n) | n × log n |
| 9 | Inner loop runs i times | O(n²) | 0 + 1 + ... + n ≈ n²/2 |
| 10 | Three nested n loops | O(n³) | n × n × n |
| 11 | Search through a list | O(n) | May examine every element |
| 12 | users[name] using dictionary | O(1) average | Hash-table lookup |
| 13 | arr.sort() + loop | O(n log n) | Sorting dominates O(n) loop |
| 14 | Loop + x in values where values is a list | O(n²) | n searches × O(n) search |
| 15 | Loop + x in values where values is a set | O(n) average | n × O(1) set lookup |
| 16 | example(n - 1) once | O(n) | One recursive call per level |
| 17 | Two example(n - 1) calls | O(2ⁿ) | Two branches at every level |
| 18 | n work inside log n loop | O(n log n) | n × log n |
| 19 | log n loop inside log n loop | O(log² n) | log n × log n |
| 20 | Inner loop starts at i | O(n²) | Approximately n²/2 operations |
Python Big-O Interview Questions
Find 20 interview-style straightforward questions in tabular format below.
| # | Interview Question | What to Identify |
|---|---|---|
| 1 | What is the time complexity of accessing arr[i] in a Python list? | Time complexity |
| 2 | What is the time complexity of x in my_list? | Average/worst case |
| 3 | What is the time complexity of x in my_set? | Average case |
| 4 | What is the complexity of dict[key]? | Average case |
| 5 | What is the complexity of arr.append(x)? | Amortized complexity |
| 6 | What is the complexity of arr.insert(0, x)? | Time complexity |
| 7 | What is the complexity of arr.pop()? | Time complexity |
| 8 | What is the complexity of arr.pop(0)? | Time complexity |
| 9 | What is the complexity of arr.sort()? | Time complexity |
| 10 | What is the complexity of this code? | Nested loops |
| 11 | What is the complexity of this code? | Logarithmic loop |
| 12 | What is the complexity of this code? | n × log n |
| 13 | What is the complexity of this code? | Triangular loop |
| 14 | What is the complexity of this recursive function? | Recursion |
| 15 | What is the complexity of this recursive function? | Recursion tree |
| 16 | Can O(n²) ever be faster than O(n)? | Big-O interpretation |
| 17 | What is the difference between O(n) and O(2n)? | Simplification |
| 18 | What is the difference between average and worst-case complexity? | Complexity concepts |
| 19 | What is space complexity? | Memory usage |
| 20 | Given two solutions, which has better asymptotic complexity? | Comparison |
