# CS代考 THE UNIVERSITY OF NEW SOUTH WALES – cscodehelp代写

THE UNIVERSITY OF NEW SOUTH WALES
3. INTEGER MULTIPLICATION I
Raveen de Silva,
office: K17 202
School of Computer Science and Engineering UNSW Sydney
Term 3, 2021

1. Master Theorem 1.1 Statement
1.2 Examples
1.3 Proof
2. Arithmetic Operations
2.1 Applying D&C to multiplication of large integers 2.2 The Karatsuba trick
3. Puzzle

1. Master Theorem 1.1 Statement
1.2 Examples
1.3 Proof
2. Arithmetic Operations
2.1 Applying D&C to multiplication of large integers 2.2 The Karatsuba trick
3. Puzzle

Master Theorem
Setup
Let:
a ≥ 1 be an integer and and b > 1 be a real number;
f (n) > 0 be a non-decreasing function defined on the positive integers;
T(n) be the solution of the recurrence
T (n) = a T (n/b) + f (n).
Define the critical exponent c∗ = logb a and the critical polynomial nc∗.

Master Theorem
Theorem
1. Iff(n)=O(nc∗−ε)forsomeε>0,thenT(n)=Θ(nc∗);
2. Iff(n)=Θ(nc∗),thenT(n)=Θ(nc∗ logn);
3. If f(n) = Ω(nc∗+ε) for some ε > 0,and for some c < 1 and some n0, af (n/b)≤cf(n) (1) holds for all n > n0,then T (n) = Θ(f (n));
Exercise
Prove that f (n) = Ω(nc∗+ε) is a consequence of (1).

Master Theorem
Theorem (continued)
4. If none of these conditions hold, the Master Theorem is NOT applicable.
Often, the proof of the Master Theorem can be tweaked to (asymptotically) solve such recurrences anyway! An example is T (n) = 2T (n/2) + n log n.

Master Theorem
Remark
Recall that for a,b > 1, loga n = Θ(logb n), so we can omit the base and simply write statements of the form f(n) = Θ(g (n) log n).
However, nloga x is not interchangeable with nlogb x – the base must be specified in such expressions.

1. Master Theorem 1.1 Statement
1.2 Examples
1.3 Proof
2. Arithmetic Operations
2.1 Applying D&C to multiplication of large integers 2.2 The Karatsuba trick
3. Puzzle

Master Theorem
Example 1
Let T (n) = 4 T (n/2) + n.
Then the critical exponent is c∗ = logb a = log2 4 = 2, so the
critical polynomial is n2.
Now, f (n) = n = O(n2−ε) for small ε (e.g. 0.1).
This satisfies the condition for case 1, so T(n) = Θ(n2).

Master Theorem
Example 2
Let T (n) = 2T (n/2) + 5 n.
Then the critical exponent is c∗ = logb a = log2 2 = 1, so the
critical polynomial is n.
Now, f (n) = 5 n = Θ(n).
This satisfies the condition for case 2, so T (n) = Θ(n log n).

Master Theorem
Example 3
Let T (n) = 3 T (n/4) + n.
Then the critical exponent is c∗ = log4 3 ≈ 0.7925, so the critical
polynomial is nlog4 3.
Now, f (n) = n = Ω(nlog4 3+ε) for small ε (e.g. 0.1). Also,af(n/b)=3f(n/4)=3/4n 0.
Therefore the Master Theorem does not apply!

Master Theorem
Exercise
Prove (2), that is, for all ε > 0, c > 0 and N > 0 there is some n > N such that