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.
Image
Common Big-O Complexities

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 # Quadratic time complexity O() 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
Explore Answers
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Image
Grokking Data Structures & Algorithms for Coding Interviews
Image
Grokking System Design Fundamentals