Big O Examples and Practice

The examples below will help you build a better understanding of how to read and interpret time complexity.

Example 1

void constantExample(int arr[]) {
    int x = arr[0];           // O(1) - Direct access
    x += 5;                   // O(1) - Single operation
    printf("%d\n", x);        // O(1) - Single output
    int y = arr[0] * 10;      // O(1) - Direct access
    y += 3;                   // O(1) - Single operation
    printf("%d\n", y);        // O(1) - Single output
}

The function accesses specific elements and performs a fixed number of operations. No matter the input size, it runs in constant O(1) time.

Example 2

void linearExample(int arr[], int n) {
    int sum = 0;                     // O(1)
    for (int i = 0; i < n; i++) {    // O(n)
        sum += arr[i];               // O(1) - Runs n times
    }
    printf("%d\n", sum);             // O(1)
}

This code iterates through the array once.

• If n = 3, it runs 3 times

• if n = 5, it runs 5 times

• and if n = 7, it runs 7 times.

The runtime for this function is linear O(n)

Example 3

void findTarget(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {          // O(n)
        if (arr[i] == target) {            // O(1) - Conditional check
            printf("Found %d\n", target);  // O(1)
            return;                        // Exits if found
        }
    }
    printf("Not Found\n");                 // O(1)
}

This code stops when it finds target, so it may not run all n times.

In the worst case, it runs n times, so the runtime is linear O(n).

Example 4

void printAllPairs(int arr[], int n) {
    for (int i = 0; i < n; i++) {         // O(n)
        for (int j = 0; j < n; j++) {     // O(n)
            printf("(%d, %d)\n", i, j);   // O(1)
        }
    }
}