7: Analysis

Question 1

Define asmptotic complexity

Answer 1

The degree to which an algorithm (or its subprocesses) become more complex or the nuber of required operaions becomes greater in number as the length of the input lengpth increases.

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

When is an algorithm in the exponential class of time compelxity?

Answer 3

When the exponent in an exponential is (a) variable, e.g. length of array as input.

Question 4

What is loop hoisting?

Answer 4

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

Question 5

What is the lower bound on sorting comparables? Assume involves comparisons of whole comparable objects being sorted and not other properties or fields, such as sort keys.

Answer 5

Minimum time complexity Ω(nlog(n))

Question 6

What are sort keys?

Answer 6

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 7

What’s the proof of the lower bound for sorting?

Answer 7

Proof for minimum time complexity Ω(nlog(n)) for sorting algorithms:

For a list of n elements, there are n! different possible orderings of the elements.

A comparison has 2 results: which of 2 elements to put 1st. With k comparisons made to sort the list and comparisons involved in the whole algorithm, this results in 2 ^ k choices.

2 ^ k must be >= n! since we have to distinguish between all the different possible orderings, of which there are n!.

This is true when k >= log2(n!)

Via Stirling’s approximation, log2(n!) is Ω(nlog(n)) worst case.

Question 8

What would P != NP actually mean?

Answer 8

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

Question 9

What are P problems? What does P stand for?

Answer 9

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 10

What are NP problems? What does NP stand for?

Answer 10

NP problems have no proof showing they can be solved in polynomial time by a deterministic TM but do have a proof showing they can be verified in polynomial time by a deterministic TM.

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

NP stands for Nondeterministic Polynomial, since solvable in polynomial time only nondeterministically and not deterministically.

Question 11

What are NP-hard problems?

Answer 11

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

Question 12

What are NP-complete problems?

Answer 12

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 13

What is verification?

Answer 13

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 14

What do divide and conquer algorithms do?

Answer 14

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

Question 15

What is a recurrence relation?

Answer 15

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

Question 16

What is the mathematical definition of a recurrence relation?

Answer 16

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 17

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

Answer 17

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

Question 18

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

Answer 18

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 19

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

Answer 19

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 20

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

Answer 20

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

Question 21

What is the Master Theorem’s general form?

Answer 21

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

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

Question 22

What is the first Master Theorem case?

Answer 22

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

Question 23

What is the second Master Theorem case?

Answer 23

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 24

What is the third Master Theorem case?

Answer 24

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 25

What is the regularity condition?

Answer 25

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 26

What is the Karatsuba multiplication algorithm?

Answer 26

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 27

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

Answer 27

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 28

What is the first simplifying rule?

Answer 28

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 29

What is the second simplifying rule?

Answer 29

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 30

What is the third simplifying rule?

Answer 30

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 31

What is the fourth simplifying rule?

Answer 31

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 32

What is Master Theorem Avoidance?

Answer 32

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 33

What is a series?

Answer 33

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 34

What is a geometric series?

Answer 34

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.