Python Algorithms: From Basics to Optimization

You already know how to write Python code. Now it's time to write fast Python code. An algorithm is a step-by-step procedure for solving a problem — but not all procedures are equal. Some run in an instant; others grind to a halt as data grows. In this guide you'll learn how to think about algorithm efficiency, apply classic patterns like sorting and searching, and optimize a real farm ROI problem using Python's built-in tools.

What Is an Algorithm?

An algorithm is a finite, ordered set of instructions that takes some input and produces a correct output. Every time you write a function, you're implementing an algorithm. The questions that separate good algorithms from bad ones are: how many steps does it take? and how does that number grow as the input grows?

Big O Notation

Big O notation expresses how an algorithm's runtime scales with the size of its input (n). Ignore constants and lower-order terms — what matters is the shape of the growth curve.

• O(1) — constant: runtime doesn't change regardless of input size. Looking up a key in a dict is O(1).
• O(n) — linear: runtime grows proportionally with input. Scanning a list once with a for loop is O(n).
• O(n log n): slightly worse than linear. Python's built-in sorted() uses Timsort, which is O(n log n).
• O(n²) — quadratic: runtime grows with the square of input. A nested loop over the same list is O(n²). Avoid on large data sets.
• O(2ⁿ) — exponential: blows up fast. Trying every possible subset of items is exponential — practical only for tiny inputs.

Sorting

Python's sorted() function (or list's .sort() method) handles sorting out of the box with an efficient O(n log n) algorithm. Use the key parameter to sort by a computed value.

crops = [
    {"name": "pumpkin", "value": 60, "cost": 20},
    {"name": "wheat",   "value": 25, "cost": 10},
    {"name": "carrot",  "value": 15, "cost": 5},
    {"name": "tomato",  "value": 40, "cost": 15},
]

# Sort by sell value, highest first
by_value = sorted(crops, key=lambda c: c["value"], reverse=True)
for c in by_value:
    print(c["name"], c["value"])
# pumpkin 60 / tomato 40 / wheat 25 / carrot 15

# Sort by ROI: (value - cost) / cost
by_roi = sorted(crops, key=lambda c: (c["value"] - c["cost"]) / c["cost"], reverse=True)
print(by_roi[0]["name"])   # pumpkin  (ROI = 200%)

Bubble Sort — a learning exercise

Bubble sort is O(n²) and far slower than Python's built-in sort. However, it's a classic teaching example because the concept is easy to visualize: repeatedly swap adjacent elements that are out of order until no swaps are needed.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break   # already sorted — early exit
    return arr

values = [40, 10, 25, 5, 60]
print(bubble_sort(values))   # [5, 10, 25, 40, 60]
# Always prefer sorted() in production code!

Linear Search vs. Binary Search

Linear search scans every element until it finds the target — O(n) in the worst case. Binary search requires a sorted list but slashes the search space in half on each step — O(log n).

def linear_search(items, target):
    """O(n) — works on unsorted lists."""
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1   # not found

def binary_search(sorted_items, target):
    """O(log n) — requires sorted input."""
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

prices = [5, 10, 15, 25, 40, 60]
print(binary_search(prices, 25))   # 3  (index)
print(binary_search(prices, 99))   # -1 (not found)

# Python's bisect module also does binary search
import bisect
idx = bisect.bisect_left(prices, 25)
print(prices[idx] == 25)   # True

Greedy Algorithms

A greedy algorithm builds a solution step-by-step, always picking the locally best option at each step. It doesn't reconsider past choices. Greedy works well when local optima add up to a global optimum — which is true for many resource allocation problems.

def plant_greedy(crops, gold, plots_available):
    """
    Greedy: keep buying the highest-ROI crop that fits in our budget,
    until we run out of gold or plot space.
    """
    plan = []
    # Sort once by ROI descending — O(n log n)
    ranked = sorted(
        crops,
        key=lambda c: (c["value"] - c["cost"]) / c["cost"],
        reverse=True
    )
    for crop in ranked:
        while gold >= crop["cost"] and plots_available > 0:
            plan.append(crop["name"])
            gold -= crop["cost"]
            plots_available -= 1
    return plan, gold

crops = [
    {"name": "wheat",   "cost": 10, "value": 25},
    {"name": "carrot",  "cost": 5,  "value": 15},
    {"name": "pumpkin", "cost": 20, "value": 60},
]
plan, leftover = plant_greedy(crops, gold=50, plots_available=4)
print(plan)      # ['pumpkin', 'pumpkin', 'carrot']
print(leftover)  # 15

Optimization Example: Maximize Farm ROI

The central optimization challenge in GrowBit is choosing which crops to plant to maximize gold earned per season given a budget and a fixed number of plots. Here's the full solution — brute force first, then the clean one-liner.

crops = [
    {"name": "wheat",   "cost": 10, "value": 25},
    {"name": "carrot",  "cost": 5,  "value": 15},
    {"name": "tomato",  "cost": 15, "value": 40},
    {"name": "pumpkin", "cost": 20, "value": 60},
]

# Brute force: calculate ROI for every crop and pick the best
best = None
best_roi = -1
for crop in crops:
    roi = (crop["value"] - crop["cost"]) / crop["cost"]
    if roi > best_roi:
        best_roi = roi
        best = crop

print(f"Best: {best['name']} at {best_roi*100:.0f}% ROI")

# One-liner using max() with a lambda key
best = max(crops, key=lambda c: (c["value"] - c["cost"]) / c["cost"])
print(f"Best: {best['name']}")   # pumpkin

Practical Tips for Faster Code

You don't need to memorize algorithms to write efficient Python. These practical rules cover 90% of real-world cases:

• Use a dict for O(1) lookups. If you're searching a list for the same value repeatedly, convert the list to a set or dict first.
• Avoid nested loops on large data. An O(n²) double-loop over 10,000 items = 100,000,000 iterations. Restructure with a dict lookup instead.
• Use Python's built-ins. sorted(), min(), max(), sum(), and any()/all() are implemented in C and much faster than equivalent Python loops.
• Sort once, query many times. If you need to find the top item repeatedly, sort the list once upfront rather than scanning it on every query.

# Slow: O(n) search repeated m times = O(n*m)
def has_crop_slow(plot_list, target):
    for plot in plot_list:
        if plot["name"] == target:
            return True
    return False

# Fast: O(1) lookup after O(n) build — pays off after first query
plot_index = {p["name"]: p for p in plot_list}

def has_crop_fast(name):
    return name in plot_index

Connect to GrowBit: Mission 15+

GrowBit's later missions challenge you to write exactly these kinds of optimization functions inside the game's Python sandbox. In Mission 15, you're given a crop database and a budget and asked to write code that maximizes total profit — no hand-holding, just a blank function to fill in. Mission 16 introduces a harvest scheduler where the order you harvest crops affects your total yield, making sorting algorithm knowledge directly applicable.

The concepts in this article — Big O awareness, the max()/sorted() key pattern, and greedy selection — are the exact tools you'll apply. By the time you reach those missions, the code will feel natural.