Exercice

Question 1

void foo(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);
}

Answer 1

O(n)

Example 1 p46

Question 2

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

Answer 2

O(n^2)

Example 2 p46

Question 3

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

Answer 3

O(n^2)

example 3 p46

Question 4

void printUnorderedPairs(int[] arrayA, int[] arrayB){
  for (int i = 0; i < arrayA.length; i++) {
    for (int j = 0; j < arrayB.length; j++) {
      if (arrayA[i] < arrayB[j]) {
        System.out.pirntln(arrayA[i] + "," + arrayB[j]);
      }
   }
}

Answer 4

O(AB)

example 4 p 47

Question 5

void printUnorderedPairs(int[] arrayA, int[] arrayB) {
  for (int i = 0; i < arrayA.length; i++) {
    for (int j = 0; j < arrayB.length; j++) {
      for(int k = 0; k < 10000; k++) {
        System.out.println(arrayA[i] + "," + arrayB[j]);
    }
  }
}

Answer 5

O(AB)

example 5 p 48

Question 6

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

Answer 6

O(N)

example 6 p48

Question 7

O(N+P) == O(N) ? where P < (N/2)

Answer 7

yes, if P < (N/2) we know that N is the dominant term so we fcan drom the O(P)

Question 8

O(2N) == O(N) ?

Answer 8

yes since we drop constants

Question 9

O(N + log(N)) == O(N) ??

Answer 9

yes O(N) dominates O(logN) so wen can drop O(logN)

Question 10

O(N+M) == O(N) ??

Answer 10

There is no established relationship between N and M so we have to keep both variables in there

Question 11

What is the complexity of an algorithm that take in an array of strings, sort each string, and then sort the full array ?

Answer 11

O(a*s(log a + log s))
with a s the length of the longest string and a the length of the array
Example 8 p49

Question 12

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

Answer 12

O(N)

example 9 p49

Question 13

boolean isPrime(int n) {
  for (int x = 2; x * x <= n ; x++) {
    if (n % x == 0) {
      return false;
  }
  }
return true;
}

Answer 13

O(sqrt(n)) square root

Example10p50

Question 14

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

Answer 14

O(N)

example 11 p 51

Question 15

void permutation(String str) {
  permutation(str,"");
}

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

Answer 15

O(N^2 * N!)

N! -> N factorial
Example 12 p 51

Question 16

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

Answer 16

O(2^N)

example 13 p53

Question 17

void allFib(int n) {
  for (int i = 0; i < n; i++) {
    System.out.println(i + ": " + fib(i));
  }
}

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

Answer 17

O(2^N)

example 14 p53