Big-O Examples

Examples

1

What is the runtime of this code?

void printSumAndProduct(int[] array) {
    int sum = 0;
    int product = 1;
    for (int i = 0; i < array.length; I++) {
        sum += array[i];
    }
    for (int i = 0; i < array.length; i++) {
        product *= array[i];
    } 
    System.out.println(sum + ", " + product);
}

The runtime would be O(N) - Even if there are two iterations on the same data set. We agreed to get rid from all constants like N2.

2

What is the runtime of this code?

void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

The would runtime be O(N * 2). There is a loop that iterates N times and another inside that also iterates N times.

3

What about this code that has an inside loop with i + 1

void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

This would give us something like:

(1, 2) (1, 3) (1, 4) (1, 5)

(2, 3) (2, 4) (2, 5)

(3, 4) (3, 5)

(4, 5)

Runtime would be O(N * 2). It is important to know that although the inside loop is smaller than the outside, it is not important to go into the details or create constants.

4

What is the runtime of this code that has two different arrays?

void printArrays(int[] arrayA, int[] arrayB) {
    for(int a : arrayA) {
        for(int b: arrayB) {
                if(a > b) {
                    System.out.println(a + “, “ + b);
                }
        }
    }
}

As we have seen on the previous page - if we had a normal loop, in this case arrayA, the runtime would be O(N). But since we have a loop inside a loop, the time would be multiplied since the data sets are different, giving us a time of O(A * B).

5

What would happen if in the same code we introduce another internal loop that has a constant value?

void printArrays(int[] arrayA, int[] arrayB) {
    for(int a : arrayA) {
        for(int b: arrayB) {
            for (int i = 0; i < 1000000; i++) {
                System.out.println(a + ", " + b);       
            }
        }
    }
}

Always remember that we will not take the constants into consideration. Therefore time remains as O(A * B).

6

And this runtime that leaves the elements of an array in reverse? Notice that the loop only makes half the array

static void reverse(int[] array) {
    for (int i = 0; I < array.length / 2; I++) {
        int other = array.length - I - 1;
        int temp = array[I];
        array[I] = array[other];
        array[other] = temp;
    }
}

The answer remains the same O(N) - since there is only one set of data and operations with N, since the fact that the loop is only done in half would create a constant that we do not need.

7

Which of the following examples do you think are equal to O(N)?

// 1.) O(N + P), en donde P = N/2
// 2.) O(2N)
// 3.) O(N + M)

The first is equal to O(N) since P is derived from N. The second we know what O(N) is also why we have to leave the constants. The last one remains as it is since it is a sum between different data sets.

8

We go with a more difficult example, if I would tell you that we have an array with strings - and we have to sort each string in the array and then sort the entire array, how would you do it?

String[] strings = {“zxc”, "acd", "ddd", "hola"};

Since this problem is longer I will try to break it into small pieces. Here we must understand that we have two variables from the beginning - the 1st being the longest string length, we will call it S. The second being the size of the array, we will call it A.

  1. We know that the time to sort a string is O(S log S),
  2. We know that we have to do this for every string we have - giving us O(A * S log S)
  3. Now we have to sort all array strings - this is another small problem within the problem. To compare a String we need a time of O(S), and we have to make an amount of O(A log A) within the array. This leaves us with a time of O(A * S log A).
  4. If we now add both parts we would have a time of O(A * S (log A + Log S))

Do not let this example demotivate you since it is a complex thing - it is good to only begin to have intuition for it, even if you do not understand it in depth.

9

What would happen if we have a Binary Tree and want to add the values of all the nodes?

int sumNodes(Node node) {
    if (node == null) return 0;
    return sumNodes(node.right) + node.value + sumNodes(node.left);
}

If we remember the recursion formula of the previous chapter, we could see that it is an exponential algorithm because of its N, O(Depth ^ Branches). In this case we have two recursive calls and N would be the number of nodes in the chain, so there would be O(2 ^ N). Some people would say that O(2 ^ Log N) would be more correct in this case - and that it could be simplified to O(N), but it would be acceptable to say O(2 ^ N).

10

What do you think of this also recursive algorithm that calculates the factorial function of a number?

int factorial(int n) {
    if (n < 0) return -1;
    if (n == 0) return1;
    return n * factorial(n - 1);
}

Here we have a simple recursive call that would go from n - 1, * n - 2, * n - 3 etc. In this case this would be simplified to O(N).

11

Lets have a look at a more complex problem

void permutation(String string) {
    permutation(string, “”);
}

void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

This algorithm will print every possible permutation of a word - Imagine doing it with ABC.

A permutation is all possible ways in which a data set can be ordered. In this case it would be like ABC, ACB, BAC, BCA, CAB, CBA. In this type of algorithm, something similar to factorial occurs where the function will be called N! Number of times (N being the string length). If N is of length () 4 then it would be called 4 * 3 * 2 * 1.

12

Lets look at a function that computes N Fibonacci

int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Generally speaking when we see an algorithm with multiple recursive calls we know that it is O(Branches ^ Depth). In this case O(2 ^ N),

13

What would happen if we use a very famous technique called Memoization (it is a way to optimize recursive functions by saving pre-computed results)

void allFib(int n) {
    int[] memo = new int[n+1];
    for (int I = 0; I < n; I++) {
        System.out.println(I + “: “ + fib(I, memo));
    }
}

int fib(int n, int[] memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] > 0) return memo[n];
    
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
   return memo[n]; 
}

This would optimize the algorithm completely as it would change the time from (2 ^ N) to O(N), a drastic improvement! This means that instead of re-computing all previous values to reach the next number - the algorithm only references them within the array of pre-computed values. This makes it a constant value.

14

What do you think of this algorithm that prints all the powers of 2. 2,4,8,16,32,64.

int powersOf2(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    int prev = powersOf2(n / 2);
    int cur = prev * 2;
    System.out.println(cur);
    return cur;
}

If we really see what is happening with this algorithm, it keeps dividing N by 2 inside of each operation. So it looks more like a type of function like that of a Binary Tree. Therefore the time would be O(Log N).

Last updated on 3/3/2020
← Big-O NotationBig-O Exercises →