Big-O Exercises

Exercises

1

This code computes the product of two variables, what is the runtime of this code?

int product(int a, int b) {
    int sum = 0;
    for (int I = 0; I < b; I++) {
        sum += a;
    }
    return sum; 
}

2

This code computes A ^ B, what would be the runtime?

static int power(int a, int b) {
    if (b < 0) return a;
    if (b == 0) return 1;
    int sum = a;
    for (int I = 0; I < b - 1; I++) {
        sum *= a;
    }
    return sum;
}

3

This code computes A% B, what would be the runtime?

int mod(int a, int b) {
    if (b <=a) return -1;
    int div = a / b;
    return a - div * b;
}

4

This code computes a division between whole integers (assuming both are positive), what would be the runtime?

int div(int a, int b) {
    int count = a;
    int sum = b;
    while (sum <= a) {
        sum += b;
        count++;
    }
    return count;
}

5

The following code calculates the square root of an integer. If the number is not a perfect square (there is no whole square root), then return -1. If N is 100, first guess if N is 50. Too high? Try something lower, halfway between 1 and 50, etc. What is the big-o?

int sqrt(int n) {
    return sqrt_helper(n, 1, n);
}
int sqrt_helper(int n, int min, int max) {
    if (max < min) return -1;
    int guess = (min + max) / 2;
    if (guess * guess == n) {
        return guess;
    } else if (guess *guess <n) {
        return sqrt_helper(n, guess + 1, max) ; 
    } else { 
        return sqrt_helper(n, min, guess - 1);
    }
}

6

The following code calculates the square root of an integer. If the number is not a perfect square (there is no whole square root), then return -1. It does so by trying larger and larger numbers until it finds the correct value (or is too high). What is your runtime?

int sqrt(int n) {
    for (int guess = 1; guess * guess < n; guess++) {
        if (guess * guess == n) return guess;
    }
    return -1;
}

7

If a binary search tree (BST) is not balanced, how long could it take in the worst case to find an item?

8

What would be the worst case if we are looking for a value in a binary tree (Binary Tree - BT) that is not ordered?

9

The appendToNew method adds a value to an array by creating a new, longer array and returning this longer array. How long does it take to copy the array?

int[] copyArray(int[] array) {
    int[] copy = new int[0];
    for (int value : array) {
        copy = appendToNew(copy, value);
    }
    return copy;
}
int[] appendToNew(int[] array, int value) {
    int[] bigger = new int[array.length + 1];
    for (int I = 0; I < array. length; I++) {
        bigger[I] = array[I];
    }
    bigger[bigger.length - 1] = value; 
    return bigger;
}

10

The following code adds the digits of a number. What is your runtime?

int sumDigits(int n) { 
    int sum = 0; 
    while (n > e) { 
        sum += n % 10; 
        n /= 10; 
    } 
    return sum; 
} 

11

The following code calculates the intersection (the number of elements in common) of two Arrays. Assuming that no Array has duplicates. Calculate the big-O notation of the intersection function which is ordering Array B and then iterating through Array A - making a check (Binary Search) if each value is in B. What is its execution time?

int intersection(int[] a, int[] b) { 
    mergesort(b);
    int intersect =0;
    
    for (int x : a) {
        if (binarySearch(b, x) >= 0) {
            intersect++;
        } 
    }
   
    return intersect;
}

Answers

1. O(B) It would be Linear runtime on B, since the loop only iterates on B.
2. O(B) It would be Linear runtime on B, since the loop only iterates on B.
3. O(1) Constant Runtime
4. O(A / B) The count variable will eventually be A / B. The While loop will eventually iterate the same as A / B.
5. O(Log N) This algorithm is essentially doing a binary search to find the square root.
6. O(Square Root(N)). This is a simple loop that for when we find guess * guess > N. In other words guess > sqrt (N).
7. O(N), where N is the number of leaves in the tree. The maximum possible time would be the depth of the tree.
8. O(N), without any order - we would have to look all the nodes in the tree.
9. O(N ^ 2) where N is the number of elements in the array.
10. O(Log N) The runtime would be the number of digits in the number.
11. O(B log B + A log B), First we have to order the Array B - which entails B Log B. Then for each element in Array A - we will do a binary search in Log B, which would remain as A Log B.