big-0.md

Big O notation instructor notes

• Explain what Big O Notation is.
• Explain why Big O Notation is useful
• Calculate Big O.

What is Big O notation?

Turn to your neighbor and explain what Big O notations is.

Why is Big O notation important?

Turn to your neighbor and explain why Big O notation is important

How do you calculate the Big O of algorithms?

What is the runtime of the code below?

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

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

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

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

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

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

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