minte9
LearnRemember   ALGORITHMS







PVM / Python / Data Structures / Time Complexity

1. Big-O Notation

Computer scienties have borrowed the concept from mathematics. Big-O is focusing on the number of steps, but in a specific way. The focus is on how fast steps grow, not exact counts. Constants and small differences are ignored. Big-O answers the question: What happens to performance when the input becomes very large?

2. Linear Search - O(n)

Linear search checks each element one by one until the target is found. In the worst case, every element must be checked. Steps grow directly with the number of elements O(n). As analogy, it is like looking for a name in an unsorted contact list by scanning from top to bottom. In the best case when item is first, time complexity is O(1). In the worst case when item is last or missing, time complexity is O(n). 
 py
contacts = ['Alice', 'Bob', 'Carol', 'Dave', 'Eve']

# Find a name in a contacts list
def find_contact(contacts, name):
    steps = 0

    # Loop through items
    for i in range(len(contacts)):
        steps += 1

        # Found at index i after steps number of checkes
        if name == contacts[i]:
            return i, steps  

    # Not found
    return -1, steps

# Linear search
(index, steps) = find_contact(contacts, 'Dave')

# Found at index: 3 steps: 4
print(f"Found at index: {index} Steps: {steps}")

3. Binary Seach - O(log n)

Binary search reapeatedly split the search in half. It repeatedly discard the half that cannot contain the target. Binary search can work only only on sorted lists. Each step cuts the search space in half. Doubling the data adds only one extra step O(log n). Compare the middle element to the target, if equal we're done. If target is greater, search the right half. If smaller, search the left half. As analogy, it is like finding a word in a dictionary by jumping to the middle, then narrowing the seaction each time. Time complexity is O(log n) comparisons in the worst case. We use it when we need fast lookups (much faster than linear search). 
 py
# Algorithmm
# ===========================
def binary_search(items, val):
    # Initialize left and right boundaries
    left = 0
    right = len(items) - 1

    # Counter to track iterations
    steps = 0

    # Search while the interval is valid
    while left <= right:
        steps += 1

        # Middle index of the current search
        middle = (left + right) // 2

        # Check if middle value is the target
        if val == items[middle]:
            return middle, steps  # Target found

        # Target value is greater, ignore the left half
        if val > items[middle]:
            left = middle + 1
        else:
            # Otherwise, ignore right half
            right = middle -1

    # Target not found, return -1 and total steps
    return -1, steps

# Using algorithm
# ===================================

# Small ordered list
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
key, steps = binary_search(data, 7)
print(f"Steps: {steps} / Found at key: {key}") 

# When doubling the list, the search increase with only 1 step
data = [i for i in range(21)]
key, steps = binary_search(data, 17)
print(f"Steps: {steps} / Found at key: {key}")

# Very fast for large numbers
data = list(range(100000))
key, steps = binary_search(data, 70000)
print(f"Steps: {steps} / Found at key: {key}")

"""
    Steps: 4 / Found at key: 6
    Steps: 5 / Found at key: 17
    Steps: 17 / Found at key: 70000
"""




References: