2025-02-10
1. 𝐎(1) – 𝐂𝐨𝐧𝐬𝐭𝐚𝐧𝐭 𝐭𝐢𝐦𝐞
- The runtime doesn’t change regardless of the input size.
- Example: Accessing an element in an array by its index.
arr = [1, 2, 3, 4, 5] print(arr[2]) # O(1) operation
2. 𝐎(𝐥𝐨𝐠 𝐧) – 𝐋𝐨𝐠𝐚𝐫𝐢𝐭𝐡𝐦𝐢𝐜 𝐭𝐢𝐦𝐞
- The runtime grows slowly as the input size increases. Typically seen in algorithms that divide the problem in half with each step.
- Example: Binary search in a sorted array.
def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1
3. 𝐎(𝐧) – 𝐋𝐢𝐧𝐞𝐚𝐫 𝐭𝐢𝐦𝐞
- The runtime grows linearly with the input size.
- Example: Finding an element in an array by iterating through each element.
def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1
4. 𝐎(𝐧 𝐥𝐨𝐠 𝐧) – 𝐋𝐢𝐧𝐞𝐚𝐫𝐢𝐭𝐡𝐦𝐢𝐜 𝐭𝐢𝐦𝐞
- The runtime grows slightly faster than linear time. It involves a logarithmic number of operations for each element in the input.
- Example: Sorting an array using quick sort or merge sort.
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right)</li> </ul> def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
5. 𝐎(𝐧^2) – 𝐐𝐮𝐚𝐝𝐫𝐚𝐭𝐢𝐜 𝐭𝐢𝐦𝐞
- The runtime grows proportionally to the square of the input size.
- Example: Bubble sort algorithm which compares and potentially swaps every pair of elements.
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
6. 𝐎(2^𝐧) – 𝐄𝐱𝐩𝐨𝐧𝐞𝐧𝐭𝐢𝐚𝐥 𝐭𝐢𝐦𝐞
- The runtime doubles with each addition to the input. These algorithms become impractical for larger input sizes.
- Example: Generating all subsets of a set.
def generate_subsets(nums): def backtrack(start, path): result.append(path) for i in range(start, len(nums)): backtrack(i + 1, path + [nums[i]]) result = [] backtrack(0, []) return result
7. 𝐎(𝐧!) – 𝐅𝐚𝐜𝐭𝐨𝐫𝐢𝐚𝐥 𝐭𝐢𝐦𝐞
- Runtime is proportional to the factorial of the input size.
- Example: Generating all permutations of a set.
from itertools import permutations def generate_permutations(arr): return list(permutations(arr))
What Undercode Say
Understanding runtime complexities is crucial for writing efficient algorithms, especially in competitive programming and technical interviews. Here are some Linux commands and tools that can help you analyze and optimize your code:
1. `time` Command: Measure the execution time of a program.
time python3 your_script.py
2. `perf` Tool: Analyze performance and identify bottlenecks.
perf stat ./your_program
valgrind: Detect memory leaks and profile your code.valgrind --leak-check=full ./your_program
gprof: Profile your C/C++ programs to understand function call times.gprof ./your_program
5. `htop`: Monitor system resources in real-time.
htop
6. `strace`: Trace system calls and signals.
strace ./your_program
7. `gdb`: Debug your programs to identify inefficiencies.
gdb ./your_program
8. `ps`: Display information about running processes.
ps aux | grep your_program
9. `vmstat`: Report virtual memory statistics.
vmstat 1
10. `iostat`: Monitor system input/output device loading.
iostat 1
For further reading on algorithm complexities, check out:
By mastering these concepts and tools, you can write more efficient code and excel in technical interviews. Always remember to analyze your algorithms and optimize them for better performance.
References:
Hackers Feeds, Undercode AI
