7: Analysis

Question 1

What is the regularity condition?

Answer 1

From the Master Theorem, when a problem has af * (n / b) <= c * f(n) for a sufficently large n and a constant c < 1.

Question 2

Give the notations for best, worst, and average complexities

Answer 2

Best case = Θ(n), exact upper bound
Average case = O(n), rough upper bound
Worst case = Ω(n), lower bound

Question 3

What is loop hoisting?

Answer 3

Trying to refactor program loigic to remove loops to optimise complexity/ies.

Question 4

What is the third simplifying rule?

Answer 4

If some functions g and h are upper/lower bounds for a cost, then their max or min is also an upper/lower bound for that cost.
If f = O(g), and f = O(h), then f = O(max(g, h)), f = O(min(g, h))
If f = Ω(g), and f = Ω(h), then f = Ω(max(g, h)), f = Ω(min(g, h))
If f = Θ(g), and f = Θ(h), then f = Θ(max(g, h)), f = Θ(min(g, h))

Question 5

What are sort keys?

Answer 5

Fields in items in a list that dictate the order of the list. In a database they are fields and a type of key (e.g. primary).

Question 6

What is the Master Theorem for divide-and-conquer recurrences?

Answer 6

Provides a general form of divide-and-conquer recurrences and 3 cases for them that must hold.

Question 7

What would P != NP actually mean?

Answer 7

Each NP problem would have a superpolynomial lower bound of complexity.

Question 8

What are P problems? What does P stand for?

Answer 8

P problems have proofs showing they can be solved in polynomial time by a deterministic TM. P stands for polynomial; since no N for nondeterministic, “P” problems are deterministically (and therefore also nondeterministically) solvable within polynomial (P) time.

Question 9

What is verification?

Answer 9

Verification is checking against previously found results, e.g. facotorials of BigIntegers in a HashMap in Java so you don’t need to recalculate each time.

Question 10

What are NP-hard problems?

Answer 10

NP-hard problems are all problems that NP problems can be reduced to in polynomial time by a deterministic TM.

Question 11

What are NP-complete problems?

Answer 11

NP-complete problems are problems in both NP and NP-hard. They have no existing proof they can be done in polynomial time by a deterministic TM, have a proof they can be verified in polynomial time by a deterministic TM, and can be reduced to from NP problems in polynomial time by a deterministic TM.
Note verification is checking against previously found results, e.g. facotorials of BigIntegers in a HashMap in Java so you don’t need to recalculate each time.

Question 12

What do divide and conquer algorithms do?

Answer 12

Recursively divide problems into smaller subproblems, before solving (“conquering”) the original larger problem by combining the results of solving the subproblems.

Question 13

What is a recurrence relation?

Answer 13

Recurrence relations are equations defining each element in sequences as a function of the preceding ones. They are used to define recursive functions.

Question 14

What is the mathematical definition of a recurrence relation?

Answer 14

T(x) = time taken for input size x
T(n) depends on T(m) where m < n: the time taken for each problem size depends on the size 1 less (and thereby all problem sizes smaller than it).

Question 15

How can you find the complexity of an algorithm from its recurrence relation?

Answer 15

Expand it and then apply known solutions or repeatedly guess and then verify possible complexities, usually by induction: trial and error.

Question 16

How does the trial and error method of finding the complexity of an algorithm from a recurrence relation work?

Answer 16

It involves repeatedly guessing and then verifying possible complexities; verification usually via mathematical induction.
T(n) will = T(m) another term, z; z depends on the nature of the algorithm, m < n, usually m = n - 1. When guessing T(n) is of a certain order of complexity, set the extra term to be that of the order ÷ n. For example, when trying O(n^2), set the term order as O(n).
You know the trial works when you can expand it into multiple recursive substeps, and the number of steps and complexities in each step corresponds to the nature of the algorithm. (? this relevance math induction)

Question 17

How do you solve the complexity of a problem from its recurrence relation by hand?

Answer 17

Try different n values in T(n) to try to work out a generalisation of T(n) in terms of only the base case (T(1) usually) and n - not in terms of T(m) where m < n, a usual.
You can then derive the complexity from this. You might need to use understanding of the problem, e.g. number of comparisons = k in sorting and number of decisions from them = 2 ^ k <= n!, for example substituting in k somewhere to be able to reduce a term to its complexity order only.

Question 18

What is the Master Theorem’s general form?

Answer 18

T(n) = a * T(n / b) f(n)

a and b are constants such a >= 1, b > 1

Question 19

What is the first Master Theorem case?

Answer 19

If f(n) = O(n^(logb(a-e)) for some constant e > 0, then T(n) = Θ(n ^ (logb(a)))

Question 20

What is the second Master Theorem case?

Answer 20

If f(n) = Θ(n ^ (logb(a)) * log^k(n)) for some constant k >= 0, then T(n) = Θ(n ^ (logb(a)) * log^(k 1) of (n))

Question 21

What is the third Master Theorem case?

Answer 21

If f(n) = Ω(n ^ logb(a e)) for some constant e > 0, and f(n) satisfies the regularity condition, then T(n) = Θ(f(n)).
Note the regularity condition is when a problem has af * (n / b) <= c * f(n) for a sufficently large n and a constant c < 1.

Question 22

What is the Karatsuba multiplication algorithm?

Answer 22

An algorithm allowing for the multiplication of 2 numbers with better time complexity than long multiplication, reducing best case time complexity from Θ(n ^ 2) with long multiplication down to polynomial order, exactly n ^ (log2(3)).

Question 23

What are the simplifying rules, and why are they useful?

Answer 23

They allow us to reduce the complex complexity results down to their orders, which allow us to interpret them more easily and pragmatically in terms of their consequences.

Question 24

What is the first simplifying rule?

Answer 24

If a function g is an upper/lower/tight bound for your cost, then any bound of the same type for g is also a vound of the same type for your cost.
If t = O(f), and f = O(g), then t = O(g)
If t = Ω(f), and f = Ω(g), then t = Ω(g)
If t = Θ(f), and f = Θ(g), then t = Θ(g)

Question 25

What is the second simplifying rule?

Answer 25

If a function h is an upper bound for two costs, then h is also an upper bound for the sum of these costs.
If f = O(h), and g = O(h), then f g = O(h)
If f = Ω(h), and g = Ω(h), then f g = Ω(h)
If f = Θ(h), and g = Θ(h), then f g = Θ(h)

Question 26

What is the fourth simplifying rule?

Answer 26

If some functions f1 and g1 are upper/lower/tight bounds for 2 costs, then the sum and product of these is also an upper/lower/tight bound for the products of those costs.
If f = O(f1), g = O(g1), then f g = O(f1 g1), f * g = O(g1 * g1) and analagous

Question 27

What is Master Theorem Avoidance?

Answer 27

When an algorithm doesn’t match the Master Theorem, you can attempt to represent its time complexity closed form solution or a simplified form as a summation function, i.e. mathematical series. A simplified form should be the sum to the number of nodes of the time complexity to process each node, with a node on a tree model being 1 branch of computation/recursion. Then multiply the number of nodes * the function of complexity at each node, and substitute in values for variables other than n to find worst/average/best case complexity.
(?)

Question 28

What is a series?

Answer 28

A form of notating summation function to a certain number of terms. Usually arithmetic ( /- a constant between each pair of terms) or geometric (* a constant between each pair of terms).

Question 29

What is a geometric series?

Answer 29

A series (a form of notating summation function to a certain number of terms) in which there is a constant ratio between terms, i.e. an = a(n - 1) * f, where ai is the ith term and f is some constant factor. Geometric series converge iff - 1 < f < 1.