Big O Notation
Big O notation is a mathematical notation used to describe the upper limit of the runtime of an algorithm as a function of the input size.
# Example functions to demonstrate Big O notation
# O(1) - Constant Time
def constant_time_example(arr):
return arr[0] # Accessing the first element is always O(1)
# O(n) - Linear Time
def linear_time_example(arr):
for i in arr:
print(i) # Printing all elements takes O(n) time
# O(n^2) - Quadratic Time
def quadratic_time_example(arr):
for i in arr:
for j in arr:
print(i, j) # Printing all pairs takes O(n^2) time
# Example usage
example_array = [1, 2, 3, 4, 5]
constant_result = constant_time_example(example_array)
print(f"Constant time example result: {constant_result}")
print("Linear time example:")
linear_time_example(example_array)
print("Quadratic time example:")
quadratic_time_example(example_array)
Code Explanation
1. Constant Time – O(1): The function constant_time_example accesses the first element of the list, which takes constant time regardless of the list size.
2. Linear Time – O(n): The function linear_time_example iterates through all elements of the list, making its runtime proportional to the list size.
3. Quadratic Time – O(n^2): The function quadratic_time_example iterates through all pairs of elements in the list, resulting in a runtime proportional to the square of the list size.
4. Example Usage: We create an example list and demonstrate the usage of each function to illustrate their respective Big O notations.
Time Complexity
Time complexity is a computational complexity that describes the amount of time it takes to run an algorithm.
# Example functions to demonstrate time complexity
# O(1) - Constant Time
def constant_time_example(arr):
return arr[0] # Accessing the first element is always O(1)
# O(n) - Linear Time
def linear_time_example(arr):
for i in arr:
print(i) # Printing all elements takes O(n) time
# O(n^2) - Quadratic Time
def quadratic_time_example(arr):
for i in arr:
for j in arr:
print(i, j) # Printing all pairs takes O(n^2) time
# Example usage
example_array = [1, 2, 3, 4, 5]
constant_result = constant_time_example(example_array)
print(f"Constant time example result: {constant_result}")
print("Linear time example:")
linear_time_example(example_array)
print("Quadratic time example:")
quadratic_time_example(example_array)
Code Explanation
1. Constant Time – O(1): The function constant_time_example accesses the first element of the list, which takes constant time regardless of the list size.
2. Linear Time – O(n): The function linear_time_example iterates through all elements of the list, making its runtime proportional to the list size.
3. Quadratic Time – O(n^2): The function quadratic_time_example iterates through all pairs of elements in the list, resulting in a runtime proportional to the square of the list size.
4. Example Usage: We create an example list and demonstrate the usage of each function to illustrate their respective time complexities.
Space Complexity
Space complexity is a measure of the amount of working storage an algorithm needs.
# Example functions to demonstrate space complexity
# O(1) - Constant Space
def constant_space_example(n):
count = 0 # Uses a constant amount of space
for i in range(n):
count += 1
return count
# O(n) - Linear Space
def linear_space_example(n):
arr = [] # Uses space proportional to n
for i in range(n):
arr.append(i)
return arr
# O(n^2) - Quadratic Space
def quadratic_space_example(n):
matrix = [[0] * n for _ in range(n)] # Uses space proportional to n^2
for i in range(n):
for j in range(n):
matrix[i][j] = i + j
return matrix
# Example usage
n = 5
constant_result = constant_space_example(n)
print(f"Constant space example result: {constant_result}")
linear_result = linear_space_example(n)
print("Linear space example result:", linear_result)
quadratic_result = quadratic_space_example(n)
print("Quadratic space example result:", quadratic_result)
Code Explanation
1. Constant Space – O(1): The function constant_space_example uses a fixed amount of space, regardless of the input size.
2. Linear Space – O(n): The function linear_space_example uses space proportional to the input size n. It creates a list of size n.
3. Quadratic Space – O(n^2): The function quadratic_space_example uses space proportional to the square of the input size. It creates an n x n matrix.
4. Example Usage: We demonstrate the usage of each function to illustrate their respective space complexities.
Here are the common time complexities from smallest to largest, along with examples to illustrate each:
-
O(1) – Constant Time
- Example: Accessing a specific element in an array.
def get_first_element(arr): return arr[0] - Explanation: No matter how large the array is, accessing the first element always takes the same amount of time.
- Example: Accessing a specific element in an array.
-
O(log n) – Logarithmic Time
- Example: Binary search in a sorted array.
def binary_search(arr, target): low, high = 0, len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1 - Explanation: Each step reduces the search space by half, leading to a logarithmic number of steps.
- Example: Binary search in a sorted array.
-
O(n) - Linear Time
- Example: Finding the maximum element in an array.
def find_max(arr): max_val = arr[0] for num in arr: if num > max_val: max_val = num return max_val - Explanation: The function goes through each element once, so the time grows linearly with the size of the array.
- Example: Finding the maximum element in an array.
-
O(n log n) - Linearithmic Time
-
Example: Merge sort algorithm.
def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 - Explanation: Each merge operation is linear, but it takes log n such operations, resulting in O(n log n) time complexity.
-
-
O(n^2) - Quadratic Time
- Example: Bubble sort algorithm.
def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] - Explanation: There are two nested loops, each going through the array, leading to n * n = n^2 operations.
- Example: Bubble sort algorithm.
-
O(n^3) - Cubic Time
- Example: Naive matrix multiplication.
def matrix_multiply(A, B): n = len(A) C = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): C[i][j] += A[i][k] * B[k][j] return C - Explanation: Three nested loops each going through n elements lead to n n n = n^3 operations.
- Example: Naive matrix multiplication.
-
O(2^n) - Exponential Time
- Example: Solving the Towers of Hanoi problem.
def towers_of_hanoi(n, source, target, auxiliary): if n == 1: print(f"Move disk 1 from {source} to {target}") return towers_of_hanoi(n-1, source, auxiliary, target) print(f"Move disk {n} from {source} to {target}") towers_of_hanoi(n-1, auxiliary, target, source) - Explanation: Each function call generates two more calls, leading to 2^n operations for n disks.
- Example: Solving the Towers of Hanoi problem.
-
O(n!) - Factorial Time
- Example: Generating all permutations of a string.
def permutations(string): if len(string) == 1: return [string] perm_list = [] for char in string: sub_permutations = permutations(string.replace(char, '', 1)) for perm in sub_permutations: perm_list.append(char + perm) return perm_list - Explanation: There are n! permutations for a string of length n, leading to factorial growth in operations.
- Example: Generating all permutations of a string.
These examples illustrate how different time complexities affect the running time of algorithms as the input size grows.
Recommend Resources:
Big-O Notation - For Coding Interviews NeetCode
1.5.1 Time Complexity #1 Abdul Bari
Leave a Reply