Asymptotics, Sorting and Recurrences Flashcards
What is the time complexity of an algorithm?
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.
What is the space complexity of an algorithm?
The amount of memory required by the algorithm for an input of size n.
What is the worst-case time complexity of an algorithm?
The largest possible number of basic operations needed for an input of size n. Time complexity is usually synonymous with worst-case time complexity.
If f and g are functions, what does it mean if f is O(g)?
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)
How do we establish that f is O(g(x))
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
Official definition of O(f(x))
O(f(x)) is the set of all functions g which satisfy g(x) <= C*f(x) for all x >= k
Proof that f(x) = x^2 + 2x + 1 = O(x^2) (f is in the set of functions O(x^2))
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
Product rule
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))
Sum rule
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)|})
What does it mean when f(x) is Ω(g(x))?
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)
What does it mean when f(x) is Θ(g(x))?
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)
What does it mean when f(x) is o(g(x))?
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))
What does it mean when f(x) is ω(g(x))?
g(x) is o(f(x))
The limit at infinity of f(x)/g(x) = infinity
An o(g(x)) function + an o(g(x)) function is…
o(g(x))
An O(g(x)) function + an o(g(x)) function is…
O(g(x))
A Θ(g(x)) function + an o(g(x)) function is…
Θ(g(x))
Insertion sort description
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
Insertion sort analysis
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)
Selection sort description
For each item in the list, find the smallest item in the remainder of the list and swap it with the current item
Selection sort analysis
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)
Merge sort description
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.
Merging process
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
Quick sort description
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()
The partition function
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)
