A function that grows no faster than O(n) is in the set. For example, O(n^2) means that the function grows no faster than n^2. The more formal definition for O(n^2) is that beyond a breakpoint B, f(n) is upper bounded by cn^2, where c is a constant multiplier. We can use this as an analogy for defining O(n^3), etc.. We can prove a function is in a certain O by using its formal definition, and wisely choosing a B and c.
On the other spectrum is Ω(n). This set contains all the functions that grow no slower than n. For example, Ω(n^2) contains all the functions that grow no slower than n^2: n^2, n^3, etc..
When a function is both Ω(n) and O(n), then that function is Θ(n), meaning it belongs is n.
Growth rate rankings: 1, logn, radn, n, nlogn, n^2, n^3...2^n, n^n
For the algorithm analysis part of the lecture, we learned to calculate the steps required for insertion sort and max slice.
Insertion sort: we take the worst case possible scenario to count the steps required. For example, there is 3i + 5 steps required in a loop inside a loop. The outer loop requires n-1 iterations, so we end up with sum from 1 to n-1 of 3i+5. We simplify it, and then we can compare it with O(n^2) or Ω(n^2) with its proper definition and finding B and c.
In max slice, we only calculated the upper and lower bounds. For upper bound, we can over-estimate the number of steps; for lower bound, we can underestimate the number of steps. The trivial margin of error does not affect the answer.
No comments:
Post a Comment