Lecture 3: Algorithms

Linear Search

the idea of the algorithm is to iterate across the array from left to right, searching for a specified element.

Worst Case Scenario (Linear Search)

We have to look through the entire array of n elements, either because the target element is the last element of the array or doesn’t exist in the array at all. Thereby, O( n )

Best-Case Scenario (Linear Search)

The target element is the first element of the array, and so we can stop looking immediately after we start. Thereby Ω ( 1 )

Pseudocode (Linear Search)

Repeat, starting at the first element:

• if the first element is what you’re looking for (the target), stop.

• Otherwise, move to the next element

Binary Search

the idea of the algorithm is to divide and conquer, reducing the search area by half each time, trying to find a target number. In order to leverage this power however, our array must first be sorted, else we cannot make assumptions about the array’s contents.

Binary Search (PseudoCode)

• Repeat until the (sub)array is of size 0:

• Calculate the middle point of the current (sub)array.

• If the target is at the middle, stop.

• Otherwise, if the target is less than what’s at the middle, repeat, changing the end point to be just to the left of the middle.

• Otherwise, if the target is greater than what’s at the middle, repeat, changing the start point to be just to the right of the middle.

Worst Case Scenario (Binary Search)

We have to divide a list of n elements in half repeatedly to find the target element, either because the target element will be found at the end of the last division or doesn’t exist in the array at all. Therefore, O(log n)

Best Case Scenario (Binary Search)

The target element is at the midpoint of the full array, and so we can stop looking immediately after we start. Therefore,Ω (1)

Bubble Sort

the idea of the algorithm is to move higher valued elements generally towards the right and lower value elements generally towards the left.

Pseudocode (Bubble Sort)

• Set swap counter to a non-zero value

• Repeat until the swap counter is 0:

  • Reset swap counter at 0

  • Look at each adjacent pair

    • If two adjacent elements are not in order, swap them and add one to the swap counter

Worst Case Scenario (Bubble Sort)

The array is in reverse order; we have to “bubble” each of the n elements all the way across the array, and since we can only fully bubble one element into position per pass, we must do this n times. Therefore, O(n2)

Best Case Scenario (Bubble Sort)

The array is already perfectly sorted, and we make no swaps on the first pass. Therefore, Ω(n)

Selection Sort

the idea of the algorithm is to find the smallest unsorted element and add it to the end of the sorted list

Pseudocode (Selection Sort)

Repeat until no unsorted elements remain:

• Search the unsorted part of the data to find the smallest value

• Swap the smallest found value with the first element of the unsorted part

Worst Case Scenario (Selection Sort)

We have to iterate over each of the n elements of the array (to find the smallest unsorted element) and we must repeat this process n times, since only one element gets sorted on each pass. Therefore, O( n 2 )

Best Case Scenario (Selection Sort)

Same as worst case scenario, There’s no way to guarantee the array is sorted until we go through this process for all the elements. Therefore,Ω (n²)

Stack frames/ function frames

chunks of memory memory that the system sets aside for a function to do its necessary work

stack

how function frames are arranged; consists of pushing new frames to the top and popping off used frames

Recursion

a technique/ implementation of an algorithm used to solve a problem in a way that is both interesting and easy to visualize

recursive function

function that as port of its execution, invokes itself

factorial function (n!)

defined over all positive integers; equals all of the positive integers less than or equal to n, multiplied together

two cases of every recursive function that could be apply given any input

1. The base case, which when triggered will terminate the recursive process

2. The recursive case, which is where the recursion will actually occur.

Merge Sort

the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order; leverages recursion

Pseudocode (Merge Sort)

• Sort the left half of the array (assuming n > 1)

• Sort the right half of the array (assuming n > 1)

• Merge the two halves together

Worst Case Scenario (Merge Sort)

We have to split n elements up and then recombine them, effectively doubling the sorted subarrays as we build them up. (combining sorted 1-element arrays into 2-element arrays, combining sorted 2-element arrays into 4-element arrays…). Therefore, O(n log n)

Best Case Scenario (Merge Sort)

The array is already perfectly sorted. But we still have to split and recombine it back together with this algorithm. Therefore, Ω(n log n)