Asymptotics Practice

Make sure to review Asymptotic Analysis Basics before proceeding with these problems.

Introduction

Asymptotics is a very intuition-based concept that often doesn't have a set algorithm for computing. The best way to get good at analyzing programs is to practice!

With that said, here are some problems of increasing difficulty for you to enjoy šŸ˜Š

For all of the below problems, assume that all undefined functions have a constant O(1) complexity.

Loops

What runtime does this function have?

void throwHalfOfMyItems(int n) {
    for (int i = 0; i < n; i += 1) {
        if (i % 2 == 0)
            throwItem(n);
    }
}

What runtime does this function have?

void lootShulkerBoxes(int n) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = 0; stack < n; stack += 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}

I've tweaked the previous problem a little šŸ˜ Try to spot the difference and see if it changes the runtime at all!

void lootShulkerBoxes(int n, int stacksToLoot) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = stacksToLoot; stack > 0; stack -= 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}

Recursion

The following two problems are inspired by this worksheet.

TREEEEEEEEE recursion šŸŒ³šŸŒ²šŸŒ“

void plantJungleSaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < 4; i += 1) {
            plantJungleSaplings(n - 1);
        }
    }
}

Let's replace the 4 in the previous problem with n and see what insanity ensues.

void plantCrazySaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < n; i += 1) { // This line changed
            plantCrazySaplings(n - 1);
        }
    }
}

Best and Worst Case Runtimes

Here's a case where the best case and worst case runtimes are different. Can you figure out what they are? (Let n = items.length).

Item[] hopperSort(Item[] items) {
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = items[i]; 
        int j = i - 1; 
        while (j >= 0 && items[j].compareTo(key) > 0) { 
            items[j + 1] = items[j]; 
            j = j - 1; 
        } 
        items[j + 1] = key; 
    } 
}

Here's a mutual recursion problem! What are the best and worst cases for explodeTNT(n)? What are their runtimes?

void explodeTNT(int n) {
    if (n % 2 == 0) {
        digDirts(n - 1, true);
        digDirts(n - 2, false);
    } else {
        digDirts(n / 2, true);
    }
}

void digDirts(int n, boolean isTNT) {
    if (isTNT) {
        explodeTNT(n / 2);
    }
    removeDirt(); // not implemented, assume O(1) runtime
}

Challenge Problems

These problems are quite difficult. Don't be concerned if you don't feel confident in solving them (I certainly don't).

A huge disaster :ooo

//initially start is 0, end is arr.length.
public int PNH(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    int counter = 0; 
    int result = 0;
    for (int i = start; i < end; i += 1) {
        if (arr[i] == 'a') {
            counter += 1;
        }
    }
    for (int i = 0; i < counter; i += 1) {
        result += PNH(arr, start + 1, end);
    }
    int mid = start + (end - start) / 2;
    return PNH(arr, start, mid) + PNH(arr, mid + 1, end);
}

Congrats for making it this far! By now you should be an expert in asymptotic analysis :P Here's one last problem:

//initially start is 0, end is arr.length.
public int lastOne(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    else if (arr[start] <= arr[end]) {
        return lastOne(arr, start + 1, end - 1);
    } else {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        return lastOne(arr, start + 1, end) 
        + lastOne(arr, start, end - 1) 
        + lastOne(arr, start + 1, end - 1);
    }
}

Last updated