Algorithm Basics

1
2
3
4
5
6

# Big O Examples
O(1)    - Constant: array access
O(log n)- Logarithmic: binary search
O(n)    - Linear: simple search
O(n log n)- Linearithmic: MergeSort
O(n²)   - Quadratic: bubble sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Linear Search O(n)
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

# Binary Search O(log n)
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

data = [2, 5, 8, 12, 16, 23, 38, 56]
print(f"Linear: found at {linear_search(data, 23)}")
print(f"Binary: found at {binary_search(data, 23)}")