Skip to content

CS50 Week 3: Algorithms

On algorithms, Big O notation and other difficult stuff that I forgot the moment I learned😅.

Written by Eva Dee on (about a 4 minute read).

  • Iterate across the array from left to right, trying to find the target element.

  • O(n) - on the order of n

for i from 0 to n-1
If i-th element is "value you are looking for"
return true
return false
  • Given a sorted array, divide and conquer by systematically eliminating half of the remaining elements (phone book) in the search for the target element.
if no items
return false
if middle item is "value you are looking for"
return true
else if "value you are looking for" < middle item
search left half
else if "value you are looking for" > middle item
search right half
  • Big O notion (on the order of)

  • O(n/2): Order of n/2

  • O(log2n): order of log n

  • They are approximations

🤔 How do the algorithms compare In terms of running time (slowest -> fastest)?

  • O(n2) bubble sort, selection sort, insertion sort
  • O(n log n) merge sort
  • O(n) linear search
  • O(log n) binary search
  • O(1)

🤔 And what's in the opposite end of Big O?

  • Ω Greek Omega letter used to describe the best cases (Ω of ...)

  • Ω(n2) selection sort

  • Ω(n log n) merge sort

  • Ω(n) bubble sort, insertion sort

  • Ω(log n)

  • Ω(1) linear search, binary search

Custom types permalink

🤔 What is a struct? It's a container, inside which you can put multiple other data types.

typedef struct
{
string name;
string number;
}
person;

Bubble sort permalink

  • Swap adjacent pairs of elements if they are out of order, effectively bubbling larger elements to the right and smaller ones to the left.
Repeat n-1 times (later changed to repeat until no swaps)
for i from 0 to n-2
if i'th and i+1'th elements out of order
swap them
  • Amounts to O(n2)

Selection sort permalink

  • Find the smallest unsorted element in an array and swap it with the first unsorted element of that array.
for i from 0 to n-1
find smallest item between i'th item and last item
swap the smallest item with the i'th item

Amounts to O(n2)

Merge sort permalink

  • Split the full aray into subarrays, then merge those subarrays back together in the correct order.
if only one item
return
else
sort left half of items
sort right half of items
merge sorted halves

θ Theta permalink

for describing algorithms where O andΩ values are the same

  • θ(n2) selection sort
  • θ(n log n) merge sort
  • θ(n)
  • θ(log n)
  • θ(1)

Insertion sort permalink

  • Proceed once through the array from left to right, shifting elements as necessary to insert each element into its correct place.

Recursion permalink

  • A function calling itself.

  • Classic example is the factorial: fact(n) = n * fact(n-1)

Every factorial has two cases:

  • base case: when triggered, will terminate the recursive process
  • recursive case: which is where recursion actually occurs
int fact(int n)
{
if (n == 1)
return 1;
else
// With single line returns, you can take the curly braces away.
return n * fact(n-1)'
}