Algorithms

Question 1

Define Big O notation

Answer 1

f(x) = O(g(x)) means:
there exists:
* some positive constant M
* some minimum x-value, x_o
Such that for all x > x_o
* f(x) <= M×g(x)

Basically: f(x) = O(g(x)) means
“f(x) is at least as fast as g(x)”

Question 2

Define the Limit Theorem

Answer 2

Let f(x) & g(x) be real-valued functions

Let L = lim (f(x)/g(x)) lim of x->infinity

1. If L = 0, f(x)=o(g(x)) (and thus Big O too)
2. If L = infinity, g(x)=o(f(x)) (and thus Big O too)
3. If 0 < L < infinity, f(x)=O(g(x)) and g(x)=O(f(x))

Question 3

Define L’Hopital’s rule

Answer 3

Condition:
* if lim f(x) and lim g(x) = 0 OR
* if lim f(x) and lim g(x) = infinity
Then:
lim (f(x)/g(x)) = lim (f'(x)/g'(x))   the derivative of each

Question 4

Define Little O notation

Answer 4

f(x) = o(g(x)) means
* for EVERY positive ε
There exists a constant x_ε
Such that: f(x) <= ε*g(x) for all x>= x_ε

Basically, f(x) = o(g(x)) means:
g(x) grows at a much faster rate than f(x)

If f(x) = o(g(x)), then f(x) = O(g(x)) too

Question 5

What is Big Omega (Ω)

Answer 5

Opposite of Big O

f(x) = Ω(g(x)) if g(x) = O(f(x))

Question 6

What is Big Theta (Θ)

Answer 6

If two functions are Big O of eachother

f(x) = Θ(g(x)) if f(x) = O(g(x)) and g(x) = O(f(x))

Question 7

What is a recurrence Relation

Answer 7

Is a mathematical equation
Is Not a code/algorithm.

Recursively defines a function’s values in terms of earlier values

Question 8

How do you prove the runtime of a function?

Answer 8

1. Write out its recurrence relation
2. Turn it into closed form (by expanding the recurrences & finding a pattern)
3. Do a formal proof to show the recurrence relation is equal to the closed form

Question 9

What is the Master Method

Answer 9

T(n) = aT(n/b) + O(n^d)
a, b, d must be constants

• if log_b(a) < d, then T(n) = O(n^d)
• if log_b(a) = d, then T(n) = O(n^d * log(n))
• if log_b(a) > d, then T(n) = O(n^(log_b(a)))

Question 10

Binary Search FIX

Answer 10

O(log(n))

Question 11

BubbleSort runtime?

Answer 11

Worst-case runtime: O(n^2)
* if array is in reverse order
Best-case runtime: O(n)
* if array is already sorted

Question 12

How does BubbleSort work?

Answer 12

1. Iterate through the list
2. At each step, compare element i to i+1
3. If they’re out of order, swap them
4. Continue down the list & start over until no swaps are needed

Question 13

InsertionSort runtime?

Answer 13

Worst-case: O(n^2)

Best-case: if already sorted
O(n) if backwards search,
O(nlog(n)) if binary search
* if array is already sorted

Question 14

How does InsertionSort work?

Answer 14

1. Iterate through array
2. At each element, figure out where to place it in the elements before it (already sorted)
3. Shift appropriate elements
4. Move to next element

Question 15

SelectionSort runtime?

Answer 15

O(n^2)

For ALL situations

Question 16

How does SelectionSort work?

Answer 16

1. Find the smallest element in the list
2. Swap it with the first element in the list
3. Move up 1, repeat with second smallest, swap with second element

Question 17

MergeSort runtime?

Answer 17

O(n*log(n))

For ALL situations

Merge runtime = O(n)

Question 18

How does MergeSort work?

Answer 18

1. Split array in half
2. Split those halves recursively
3. Merge the two halves with Merge

Question 19

QuickSort runtime?

Answer 19

Worst-case: O(n^2)

Average: O(n*log(n)) in expectation
* (If you split the array in half each time)

Question 20

How does QuickSort work?

Answer 20

1. Select a pivot element
2. Iterate through the array, smaller values go to left of pivot, bigger values go to right, duplicates of pivot go to a middle array
3. Recurse for left & right sub-arrays

Question 21

Principle of Divide & Conquer

Answer 21

1. Break problem into smaller subproblems
2. Recursively solve the subproblems
3. Combine the subproblem solutions to solve the OG problem

Question 22

Example of Divide and Conquer algorithms:

Answer 22

• binary search
• QuickSort
• MergeSort