Lesson 1 of 14

Data Structures and Operation Costs

A page of names can serve as a contact list. Sorting it by name makes searching easier, but now each new name needs a place in that order. How you store data affects which operations are efficient.

Three ideas to separate

• Data structure: A way to store and connect data, such as an array, linked list, or tree.
• Algorithm: A procedure that produces a result. Comparing names one by one is an algorithm.
• Abstract data type (ADT): A contract describing the available operations. A stack promises to let you add an item and remove the most recently added item. It can be implemented with an array or a linked list.

How much work does it take?

Let n be the input size. We look at how the amount of work grows as n increases. Big O describes an upper bound on that growth, not an exact duration in seconds.

• O(1): Read a specified array position. The number of steps stays roughly constant as the collection grows.
• O(n): Scan a collection once. In the worst case, inspect every item.
• O(log n): Repeatedly halve the search range in a sorted array.
• O(n²): Work grows as it does when comparing every item with every other item.

Always identify the operation and the case being considered. A sequential search can finish after one comparison if the first item matches. If the match is last or missing, it examines n items.

Recursion makes a problem smaller

Recursion means a function calls itself. This function counts down through positive integers.

def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

countdown(3)

It prints 3, 2, and 1. The condition n <= 0 tells it when to stop, and n - 1 reduces the problem. Missing either can prevent the calls from ending.

This example takes O(n) time and O(n) call space to remember where execution must return. Python limits recursion depth, so a loop may suit large inputs better.

Check your understanding

You search 1,000 unsorted contacts from the beginning. How many items must you check if the name is missing? What happens to the worst-case work when the input doubles?