Big O Cheat Sheet

You are halfway through a problem and you wonder, “Wait, is a hash table lookup fast or slow? And which sort was the cheap one again?” You know you learned this. You just can’t recall it right now.

That happens to everyone. The thing is, you don’t need to memorize all of it. You need one page you can glance at and find the answer fast. So this tutorial is that page. It’s a cheat sheet, which just means a short reference you keep nearby to look things up quickly. Bookmark it, and come back whenever your memory goes blank.

📈 Time Complexities, Fastest to Slowest

First, let’s line up the common time complexities. Time complexity describes how the work an algorithm does grows as the input gets bigger. Smaller growth is better.

Here they are, from the fastest at the top to the slowest at the bottom. As you read down the table, the same algorithm gets slower and slower on big inputs.

So the rule of thumb is simple. O(1) and O(log n) are great. O(n) and O(n log n) are fine for most work. O(n^2) starts to hurt on big inputs. And anything from O(2^n) down is something you avoid unless the input is tiny.

🗂️ Data Structure Operations

Now the part people forget most. Each data structure is fast at some things and slow at others. Picking the right one is mostly about knowing these costs.

A quick reminder of the four operations in the table:

• Access means jumping straight to an item by its position.
• Search means looking for an item when you don’t know where it is.
• Insert means adding a new item.
• Delete means removing an item.

These numbers are the average case. That means the cost you usually get in normal use, not the rare worst day.

A few things worth noticing here:

• An array gives you O(1) access because the computer can jump straight to any index. But inserting or deleting in the middle means shifting everything after it, so that’s O(n).
• A linked list is the mirror image. There is no jumping to an index, so access is O(n). Adding or removing a node just means relinking pointers, so that part is O(1). But that O(1) only counts if you are already at the spot, like the head or tail. If you first have to walk the list to find the spot, that walking is still O(n).
• A stack and a queue only ever touch one end, so their add and remove are O(1). You are not meant to search inside them, which is why search is O(n).
• A hash table is the star for lookups. It uses a key to compute where the value sits, so search, insert, and delete are all O(1) on average. There is no “access by position”, which is why access says N/A.

🔀 Sorting Algorithms

Last block, and the one interviewers love to ask about. Each sort has a time cost and a space cost.

• Time is how long the sort takes as the list grows. We list the average and the worst case, because some sorts have a bad worst case.
• Space is how much extra memory the sort needs beyond the list itself. In-place sorts need almost no extra memory, so they are O(1) on space.

Here is how to read that table in plain words:

• Bubble, selection, and insertion sort are the simple ones. They are easy to write but slow, all O(n^2). They are fine for tiny lists or for learning, not for big data.
• Merge sort is reliably O(n log n) every time, which is great. The catch is it needs O(n) extra memory to merge.
• Quick sort is usually the fastest in practice, also O(n log n) on average. But its worst case drops to O(n^2) when the pivot is chosen badly, so keep that in mind.
• Heap sort gives you a solid O(n log n) and needs almost no extra memory. That makes it a nice balance.
• Counting sort looks magical because it can beat O(n log n). The k in O(n + k) is the range of the values being sorted. It only wins when that range is small, like sorting ages or exam scores.

⌨️ Seeing O(1) vs O(n) in Code

The data structure table says array access is O(1) and array search is O(n). It helps to see that with your own eyes. Below, getByIndex jumps straight to a spot, so it never loops. But search walks the list one item at a time until it finds the target.

#include <stdio.h>

// O(1): jump straight to the index, no loop
int getByIndex(int *arr, int index) {
    return arr[index];
}

// O(n): walk the array until we find the target
int search(int *arr, int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i; // found it
    }
    return -1; // not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;

    printf("Element at index 2 (O(1)): %d\n", getByIndex(arr, 2));
    printf("Index of value 40 (O(n)): %d\n", search(arr, n, 40));
    return 0;
}

Element at index 2 (O(1)): 30
Index of value 40 (O(n)): 3

#include <iostream>
using namespace std;

// O(1): jump straight to the index, no loop
int getByIndex(int arr[], int index) {
    return arr[index];
}

// O(n): walk the array until we find the target
int search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i; // found it
    }
    return -1; // not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;

    cout << "Element at index 2 (O(1)): " << getByIndex(arr, 2) << endl;
    cout << "Index of value 40 (O(n)): " << search(arr, n, 40) << endl;
    return 0;
}

Element at index 2 (O(1)): 30
Index of value 40 (O(n)): 3

public class AccessVsSearch {
    // O(1): jump straight to the index, no loop
    static int getByIndex(int[] arr, int index) {
        return arr[index];
    }

    // O(n): walk the array until we find the target
    static int search(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i; // found it
        }
        return -1; // not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        System.out.println("Element at index 2 (O(1)): " + getByIndex(arr, 2));
        System.out.println("Index of value 40 (O(n)): " + search(arr, 40));
    }
}

Element at index 2 (O(1)): 30
Index of value 40 (O(n)): 3

# O(1): jump straight to the index, no loop
def get_by_index(arr, index):
    return arr[index]

# O(n): walk the list until we find the target
def search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # found it
    return -1  # not found

def main():
    arr = [10, 20, 30, 40, 50]
    print("Element at index 2 (O(1)):", get_by_index(arr, 2))
    print("Index of value 40 (O(n)):", search(arr, 40))

if __name__ == "__main__":
    main()

Element at index 2 (O(1)): 30
Index of value 40 (O(n)): 3

// O(1): jump straight to the index, no loop
function getByIndex(arr, index) {
    return arr[index];
}

// O(n): walk the array until we find the target
function search(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i; // found it
    }
    return -1; // not found
}

function main() {
    const arr = [10, 20, 30, 40, 50];
    console.log("Element at index 2 (O(1)):", getByIndex(arr, 2));
    console.log("Index of value 40 (O(n)):", search(arr, 40));
}
main();

Element at index 2 (O(1)): 30
Index of value 40 (O(n)): 3

See the difference? getByIndex has no loop at all, so its cost never changes no matter how big the array gets. That is O(1). search has a loop that can run once for every element, so as the array grows the work grows with it. That is O(n).

🧩 What You’ve Learned

You now have a one-glance reference for the costs that show up in almost every problem. Here’s the recap.

• ✅ Time complexities rank from O(1) and O(log n) at the fast end down to O(2^n) and O(n!) at the slow end.
• ✅ Arrays give O(1) access but O(n) insert and delete; linked lists are the opposite.
• ✅ Stacks and queues add and remove in O(1), and hash tables search, insert, and delete in O(1) on average.
• ✅ Bubble, selection, and insertion sort are O(n^2); merge, quick, and heap sort are O(n log n).
• ✅ Quick sort can drop to O(n^2) in its worst case, and counting sort can beat O(n log n) when the value range is small.

🚀 What’s Next?

A cheat sheet is for looking things up fast, but you remember it better once you understand where the numbers come from.

• Big O Notation explains what these O(…) symbols actually mean and how to read them.
• Time Complexity walks through working out the cost of a piece of code step by step.

Keep this page open while you practice, and these complexities will move from “I have to look it up” to “I just know it”.