Big O Notation 101: The Secret To Writing Efficient Algorithms

From simple array operations to complex sorting algorithms, understanding the Big O Notation is critical for building high-performance software solutions.

1 – O(1)

This is the constant time notation. The runtime remains steady regardless of input size. For example, accessing an element in an array by index and inserting/deleting an element in a hash table.

2 – O(n)

Linear time notation. The runtime grows in direct proportion to the input size. For example, finding the max or min element in an unsorted array.

3 – O(log n)

Logarithmic time notation. The runtime increases slowly as the input grows. For example, a binary search on a sorted array and operations on balanced binary search trees.

4 – O(n^2)

Quadratic time notation. The runtime grows exponentially with input size. For example, simple sorting algorithms like bubble sort, insertion sort, and selection sort.

5 – O(n^3)

Cubic time notation. The runtime escalates rapidly as the input size increases. For example, multiplying two dense matrices using the naive algorithm.

6 – O(n logn)

Linearithmic time notation. This is a blend of linear and logarithmic growth. For example, efficient sorting algorithms like merge sort, quick sort, and heap sort.

7 – O(2^n)

Exponential time notation. The runtime doubles with each new input element. For example, recursive algorithms solve problems by dividing them into multiple subproblems.

8 – O(n!)

Factorial time notation. Runtime skyrockets with input size. For example, permutation-generation problems.

9 – O(sqrt(n))

Square root time notation. Runtime increases relative to the input’s square root. For example, searching within a range such as the Sieve of Eratosthenes for finding all primes up to n.

You Should Know:

Here are some practical commands and code snippets to help you understand and apply Big O Notation in real-world scenarios:

1. O(1) Example in Python:


<h1>Accessing an element in an array by index</h1>

arr = [10, 20, 30, 40, 50]
print(arr[2]) # Output: 30

2. O(n) Example in Python:


<h1>Finding the max element in an unsorted array</h1>

arr = [10, 20, 30, 40, 50]
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
print(max_val) # Output: 50

3. O(log n) Example in Python (Binary Search):


<h1>Binary search on a sorted array</h1>

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

arr = [10, 20, 30, 40, 50]
print(binary_search(arr, 40)) # Output: 3

4. O(n^2) Example in Python (Bubble Sort):


<h1>Bubble sort implementation</h1>

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]
return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr)) # Output: [11, 12, 22, 25, 34, 64, 90]

O(n log n) Example in Python (Merge Sort):
```
</li>
</ol>

<h1>Merge sort implementation</h1>

def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[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]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

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

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

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print(arr) # Output: [3, 9, 10, 27, 38, 43, 82]
```
What Undercode Say:

Big O Notation is a foundational concept for any developer aiming to write efficient and scalable code. By understanding the time and space complexity of algorithms, you can make informed decisions about which approach to use for a given problem. Whether you’re working with small datasets or large-scale systems, mastering Big O will help you optimize performance and avoid bottlenecks.

For further reading, check out these resources:
- Big O Cheatsheet
- GeeksforGeeks: Time Complexity
Remember, the key to mastering Big O is practice. Experiment with different algorithms, analyze their performance, and apply these concepts to real-world problems. Happy coding! 🚀

References:

Reported By: Alexxubyte Systemdesign – Hackers Feeds
Extra Hub: Undercode MoN
Basic Verification: Pass ✅

Join Our Cyber World:

Whatsapp
Telegram

Listen to this Post