Asymptotics, Sorting and Recurrences

Question 1

What is the time complexity of an algorithm?

Answer 1

The number of operations carried out by that algorithm for an input of size n. These operations include addition, multiplication, comparisons, swaps, assignments, and more.

Question 2

What is the space complexity of an algorithm?

Answer 2

The amount of memory required by the algorithm for an input of size n.

Question 3

What is the worst-case time complexity of an algorithm?

Answer 3

The largest possible number of basic operations needed for an input of size n. Time complexity is usually synonymous with worst-case time complexity.

Question 4

If f and g are functions, what does it mean if f is O(g)?

Answer 4

There are constants C and k such that |f(x)| <= C|g(x)| when x >= k
This essentially means that after a certain point, f(x) never goes above Cg(x)

Question 5

How do we establish that f is O(g(x))

Answer 5

Find a pair of witness values C and k, which satisfy |f(x)| <= C*|g(x)|, x >= k
If C and k are witnesses, any values greater than C and k are also witnesses

Question 5

Official definition of O(f(x))

Answer 5

O(f(x)) is the set of all functions g which satisfy g(x) <= C*f(x) for all x >= k

Question 6

Proof that f(x) = x^2 + 2x + 1 = O(x^2) (f is in the set of functions O(x^2))

Answer 6

For all x >= 1, 1 <= x <= x^2

For all x >= 1, f(x) <= x^2 + 2x^2 + x^2 = 4x^2
f(x) <= 4x^2 for all x >= 1

Question 7

Product rule

Answer 7

If f(x) is O(g(x)) and s(x) is O(t(x)), then f(x)s(x) is O(g(x)t(x))

Question 8

Sum rule

Answer 8

If f(x) is O(g(x)) and s(x) is O(t(x)), then f(x) + s(x) is O(max{|g(x)|, |t(x)|})

Question 9

What does it mean when f(x) is Ω(g(x))?

Answer 9

There are constants C and k such that |f(x)| >= C*|g(x)| when x >= k

f(x) is Ω(g(x)) if and only if g(x) is O(f(x))

This essentially means that after a certain point, f(x) never goes below C*g(x)

Question 10

What does it mean when f(x) is Θ(g(x))?

Answer 10

f(x) is both O(g(x)) and Ω(g(x))
Or if f(x) is O(g(x)) and g(x) is O(f(x))
Beyond a certain k, Cg(x) <= f(x) <= Dg(x)
Θ(g(x)) is the set of all functions in the form p*g(x)

Question 11

What does it mean when f(x) is o(g(x))?

Answer 11

The limit at infinity of f(x)/g(x) = 0

For any positive C there exists a positive k, where beyond k, C*f(x) < g(x)

If f(x) is o(g(x)), it’s also O(g(x))

Question 12

What does it mean when f(x) is ω(g(x))?

Answer 12

g(x) is o(f(x))
The limit at infinity of f(x)/g(x) = infinity

Question 13

An o(g(x)) function + an o(g(x)) function is…

Answer 13

o(g(x))

Question 14

An O(g(x)) function + an o(g(x)) function is…

Answer 14

O(g(x))

Question 15

A Θ(g(x)) function + an o(g(x)) function is…

Answer 15

Θ(g(x))

Question 16

Insertion sort description

Answer 16

Starting with the second item in the list, each item is moved left using swaps until the item to the left of it is smaller

Question 17

Insertion sort analysis

Answer 17

Inserts the ith element into the already sorted sequence a_1, a_2, …, a_i-1 to yield the sorted sequence a_1, a_2, …, a_i-1, a_i

After the ith iteration, the first i+1 elements are in order

Running time between n-1 and n*(n-1)/2 - worst case O(n^2)

Question 18

Selection sort description

Answer 18

For each item in the list, find the smallest item in the remainder of the list and swap it with the current item

Question 19

Selection sort analysis

Answer 19

After the i-th iteration, positions 1 to i are in order

Time complexity
= Sum(i=1, i=n-1, Sum(j=i+1, j=n, 1))
= Sum(i=1, i=n-1, n-i)
= Sum(i=1, i=n-1, n) - Sum(i=1, i=n-1, i)
= n(n-1) - n(n-1)/2
= n(n-1)/2
= O(n^2)

Question 20

Merge sort description

Answer 20

Recursive:
If a given sequence has length 1, it’s sorted and we can finish.
Otherwise split the sequence into two sequences of equal length, run merge sort on both and then merge the two resulting (sorted) sequences.

Question 21

Merging process

Answer 21

We have two sorted sequences, left and right
Create an empty result sequence
Look at the leftmost element in both left and right, compare them and move the smaller one to the result sequence
If either left or right is empty, append the entire other one to the result sequence
Repeat until both left and right are empty

Question 22

Quick sort description

Answer 22

QuickSort(A, left, right)
At the beginning of each recursive call,
[QuickSort picks a pivot element from the current sequence
It moves all elements smaller than the pivot to the left of the pivot, leaving the elements bigger than the pivot on the right side]
It then calls QuickSort on both sides of the pivot and concatenates the results.

[…] = Partition()

Question 23

The partition function

Answer 23

Partition(A, left, right)
Chooses the rightmost element as the pivot (not all partition functions do this)
Sets i to left-1
Iterates through the list, whenever it finds an element smaller than the pivot it swaps it with A[i+1] and increments i
Swaps A[i+1] and A[right]
Returns i+1 (the pivot position after partitioning)