What is Big O Notation?

Big O notation is a mathematical notation that describes the efficiency or complexity of an algorithm, especially in terms of time (time complexity) and space (space complexity). It's about the worst-case scenario, giving an upper limit on the time or space an algorithm might take.

## Why Big O?

• It helps in estimating performance and understanding how an algorithm will scale.
• Crucial for comparing algorithms, especially when dealing with large inputs.
• A key part of optimizing code and making systems scalable and efficient.

## Common Big O Notations

Here are some common Big O notation with a Python coding example to illustrate how they manifest in real code.

### 1. O(1) - Constant Time

Description: The execution time remains constant regardless of input size.

Python Example:

``````def get_first_element(my_list):
return my_list[0] if my_list else None

# Constant time complexity O(1)
print(get_first_element([1, 2, 3, 4, 5]))``````

### 2. O(log n) - Logarithmic Time

Description: The execution time increases logarithmically with input size.

Python Example:

``````def binary_search(my_list, item):
low = 0
high = len(my_list) - 1
while low <= high:
mid = (low + high) // 2
guess = my_list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None

# Logarithmic time complexity O(log n)
print(binary_search([1, 3, 5, 7, 9], 3))``````

### 3. O(n) - Linear Time

Description: The execution time increases linearly with the input size.

Python Example:

``````def find_max(my_list):
max_num = my_list[0]
for num in my_list:
if num > max_num:
max_num = num
return max_num

# Linear time complexity O(n)
print(find_max([1, 2, 3, 4, 5]))``````

### 4. O(n log n)

Description: A combination of linear and logarithmic time complexities.

Python Example:

``````def merge_sort(my_list):
if len(my_list) > 1:
mid = len(my_list) // 2
left_half = my_list[:mid]
right_half = my_list[mid:]

merge_sort(left_half)
merge_sort(right_half)

i = j = k = 0

while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
my_list[k] = left_half[i]
i += 1
else:
my_list[k] = right_half[j]
j += 1
k += 1

while i < len(left_half):
my_list[k] = left_half[i]
i += 1
k += 1

while j < len(right_half):
my_list[k] = right_half[j]
j += 1
k += 1

return my_list

# O(n log n) time complexity
print(merge_sort([5, 3, 8, 6, 2, 7]))``````

### 5. O(n²) - Quadratic Time

Description: Execution time increases quadratically with the input size.

Python Example:

``````def bubble_sort(my_list):
n = len(my_list)
for i in range(n):
for j in range(0, n-i-1):
if my_list[j] > my_list[j+1]:
my_list[j], my_list[j+1] = my_list[j+1], my_list[j]
return my_list

print(bubble_sort([5, 3, 8, 6, 2]))``````

### 6. O(2^n) - Exponential Time

Description: Execution time doubles with each addition to the input data set.

Python Example:

``````def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

# Exponential time complexity O(2^n)
print(fibonacci(10))``````

### 7. O(n!) - Factorial Time

Description: Execution time grows factorially with the input size, often seen in problems involving permutations.

Python Example:

``````def permute(my_list):
if len(my_list) == 0:
return [[]]
first = my_list[0]
rest = my_list[1:]
perms_without_first = permute(rest)

all_perms = []
for perm in perms_without_first:
for i in range(len(perm) + 1):
all_perms.append(perm[:i] + [first] + perm[i:])
return all_perms

# Factorial time complexity O(n!)
print(permute([1, 2, 3]))``````

Each example demonstrates how the complexity affects the code's performance, especially noticeable with larger inputs.

## Visualizing Big O:

Imagine plotting a graph where the x-axis represents the size of the input and the y-axis represents the time or space taken by the algorithm. Each Big O notation represents a different curve on this graph, illustrating how the algorithm scales.

## Real-World Example:

Say you're running a ticket booking website. If you use a linear search (O(n)) to find available seats, it's fine for a small theater. But for a huge concert arena, this might become slow. Using a more efficient search algorithm (like binary search, O(log n)) can significantly speed up seat finding as the size of the venue increases.

Big O notation gives you a high-level understanding of how an algorithm performs and scales, making it an essential tool in a developer's toolkit, especially when dealing with large datasets or systems where performance is key.

TAGS
Coding Interview
CONTRIBUTOR
Design Gurus Team
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking Data Structures & Algorithms for Coding Interviews
Grokking System Design Fundamentals