Week 2

• Linear Search Algorithm – go from left to right the array or right to left until the target is found. – O(n)
• Binary Search Algorithm – “Divide and Conquer”. Note: the array must first be sorted before this algorithm can be used. – O(logn)
• Bubble Sort – O(n^2)
• Selection Sort – O(n^2)
• Insertion Sort – O(n^2)
• Merge Sort – utilizes recursion – O(nlogn)
• Recursive functions, in general, must have a base case (which terminates the possibility of endless recursive calls) and a recursive case.

On Algorithm Efficiency.

There’s Big O Notation, which represents the worst case scenario and is generally said to be used in describing the execution time or space used by an algorithm.

There’s also the Big Omega Notation which, unlike Big O that describes upper bounds, describes lower bounds.

In order of decreasing speed, Big O can be represented as follows:

• O(1) => Constant time
• O(logn) => Logarithmic time
• O(n) => Linear time
• O(nlogn) => Linearithmic time (log-linear time)
• O(n^2) => Quadratic time
• O(n^c) => Polynomial time
• O(c^n) => Exponential time
• O(n!) => Factorial time
• O(∞) => Infinite time

Quick notes:

A for loop with an O(1) body has a linear time complexity O(n). I.e.

for (init; check; increment) {
  // O(1) operation
}

A nested for loop with an O(1) body has a quadratic time complexity O(n^2). I.e.

for (init; check; increment) {
  for (init; check; increment) {
    // O(1) op.
  }
}