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

Question 1

What runtime does this function have?

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

Q1 Answer

Question 2a

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);
            }
        }
    }       
}

Q2a Answer

Question 2b

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);
            }
        }
    }       
}

Q2b Answer

Recursion

The following two problems are inspired by this worksheet.

Question 3

TREEEEEEEEE recursion 🌳🌲🌴

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

Q3 Answer

Question 4

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);
        }
    }
}

Q4 Answer

Best and Worst Case Runtimes

Question 5

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; 
    } 
}

Q5 Answer

Question 6

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
}

Q6 Answer

Challenge Problems

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

Question 7

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);
}

Q7 Answer

Question 8

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);
    }
}

Q8 Answer