CS计算机代考程序代写 chain AI Excel algorithm NEW SOUTH WALES

NEW SOUTH WALES
Algorithms: COMP3121/9101
School of Computer Science and Engineering University of New South Wales
3. RECURRENCES – part A
COMP3121/3821/9101/9801 1 / 22

Asymptotic notation
“Big Oh” notation: f(n) = O(g(n)) is an abbreviation for: “There exist positive constants c and n0 such that
0≤f(n)≤cg(n) for all n≥n0”.
COMP3121/3821/9101/9801 2 / 22

Asymptotic notation
“Big Oh” notation: f(n) = O(g(n)) is an abbreviation for: “There exist positive constants c and n0 such that
0≤f(n)≤cg(n) for all n≥n0”.
In this case we say that g(n) is an asymptotic upper bound for
f (n).
f(n) = O(g(n)) means that f(n) does not grow substantially faster
than g(n) because a multiple of g(n) eventually dominates f(n).
COMP3121/3821/9101/9801 2 / 22

Asymptotic notation
“Omega” notation: f(n) = Ω(g(n)) is an abbreviation for: “There exists positive constants c and n0 such that
0≤cg(n)≤f(n) for all n≥n0.”
COMP3121/3821/9101/9801 3 / 22

Asymptotic notation
“Omega” notation: f(n) = Ω(g(n)) is an abbreviation for: “There exists positive constants c and n0 such that
0≤cg(n)≤f(n) for all n≥n0.”
In this case we say that g(n) is an asymptotic lower bound for
f (n).
f(n) = Ω(g(n)) essentially says that f(n) grows at least as fast as
g(n), because f(n) eventually dominates a multiple of g(n). Since c g(n) ≤ f(n) if and only if g(n) ≤ 1c f(n), we have
f(n) = Ω(g(n)) if and only if g(n) = O(f(n)).
COMP3121/3821/9101/9801 3 / 22

Recurrences
Recurrences are important to us because they arise in estimations of time complexity of divide-and-conquer algorithms.
COMP3121/3821/9101/9801 4 / 22

Recurrences
Recurrences are important to us because they arise in estimations of time complexity of divide-and-conquer algorithms.
Merge-Sort(A, p, r)
1 ifp 1 a real number;
COMP3121/3821/9101/9801 5 / 22

Recurrences
Let a ≥ 1 be an integer and b > 1 a real number; Assume that a divide-and-conquer algorithm:
COMP3121/3821/9101/9801 5 / 22

Recurrences
Let a ≥ 1 be an integer and b > 1 a real number; Assume that a divide-and-conquer algorithm:
reduces a problem of size n to a many problems of smaller size n/b;
COMP3121/3821/9101/9801 5 / 22

Recurrences
Let a ≥ 1 be an integer and b > 1 a real number; Assume that a divide-and-conquer algorithm:
reduces a problem of size n to a many problems of smaller size n/b; the overhead cost of splitting up/combining the solutions for size n/b into a solution for size n is if f(n),
then the time complexity of such algorithm satisfies T (n) = a T 􏰃 n 􏰄 + f (n)
b
Note: we should be writing
COMP3121/3821/9101/9801
5 / 22

T (n) = a T 􏰃 n 􏰄 + f (n) b
size of instance = n size of instances = n/b
size of instances = n/b2 .
a many instances
…
….. ….. …
…
…
…. .
. .
depth of recursion: log! 𝑛
……
size of instances = 1
COMP3121/3821/9101/9801
6 / 22

Some recurrences can be solved explicitly, but this tends to be tricky.
COMP3121/3821/9101/9801 7 / 22

Some recurrences can be solved explicitly, but this tends to be tricky.
Fortunately, to estimate efficiency of an algorithm we do not need the exact solution of a recurrence
COMP3121/3821/9101/9801 7 / 22

Some recurrences can be solved explicitly, but this tends to be tricky.
Fortunately, to estimate efficiency of an algorithm we do not need the exact solution of a recurrence
We only need to find:
1 the growth rate of the solution i.e., its asymptotic behaviour;
2 the (approximate) sizes of the constants involved (more about
that later)
COMP3121/3821/9101/9801 7 / 22

Master Theorem:
Let:
a ≥ 1 be an integer and and b > 1 a real;
COMP3121/3821/9101/9801 8 / 22

Master Theorem:
Let:
a ≥ 1 be an integer and and b > 1 a real; f(n) > 0 be a non-decreasing function;
COMP3121/3821/9101/9801 8 / 22

Master Theorem:
Let:
a ≥ 1 be an integer and and b > 1 a real;
f(n) > 0 be a non-decreasing function;
T (n) be the solution of the recurrence T (n) = a T (n/b) + f (n);
COMP3121/3821/9101/9801
8 / 22

Master Theorem:
Let:
a ≥ 1 be an integer and and b > 1 a real;
f(n) > 0 be a non-decreasing function;
T (n) be the solution of the recurrence T (n) = a T (n/b) + f (n);
Then:
COMP3121/3821/9101/9801
8 / 22

Master Theorem:
Let:
a ≥ 1 be an integer and and b > 1 a real;
f(n) > 0 be a non-decreasing function;
T (n) be the solution of the recurrence T (n) = a T (n/b) + f (n);
Then:
1 If f(n) = O(nlogb a−ε) for some ε > 0, then T(n) = Θ(nlogb a);
2 If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a log2 n);
3 Iff(n)=Ω(nlogba+ε)forsomeε>0,andforsomec<1andsomen0, af (n/b) ≤ cf(n) holds for all n > n0, then T(n) = Θ(f(n));
4 If none of these conditions hold, the Master Theorem is NOT applicable.
COMP3121/3821/9101/9801
8 / 22

Master Theorem – a remark
Note that for any b > 1,
logb n = logb 2 log2 n;
COMP3121/3821/9101/9801 9 / 22

Master Theorem – a remark
Note that for any b > 1,
logb n = logb 2 log2 n;
Since b > 1 is constant (does not depend on n), we have for c = logb 2 > 0
logbn=c log2n; log2 n = 1c logb n;
COMP3121/3821/9101/9801
9 / 22

Master Theorem – a remark
Note that for any b > 1,
logb n = logb 2 log2 n;
Since b > 1 is constant (does not depend on n), we have for c = logb 2 > 0
Thus,
logbn=c log2n; log2 n = 1c logb n;
logb n = Θ(log2 n)
COMP3121/3821/9101/9801
9 / 22

Master Theorem – a remark
Note that for any b > 1,
logb n = logb 2 log2 n;
Since b > 1 is constant (does not depend on n), we have for c = logb 2 > 0
Thus, and also
logbn=c log2n; log2 n = 1c logb n;
logb n = Θ(log2 n) log2 n = Θ(logb n).
So whenever we have f = Θ(g(n) log n) we do not have to specify what base the log is – all bases produce equivalent asymptotic
estimates (but we do have to specify b in expressions such as nlogb a).
COMP3121/3821/9101/9801 9 / 22

Master Theorem – Examples
Let T (n) = 4 T (n/2) + n;
COMP3121/3821/9101/9801 10 / 22

Master Theorem – Examples
Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2;
COMP3121/3821/9101/9801 10 / 22

Master Theorem – Examples
Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2;
thus f(n) = n = O(n2−ε) for any ε < 1. COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). Let T (n) = 2T (n/2) + 5 n; COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). Let T (n) = 2T (n/2) + 5 n; thennlogba =nlog22 =n1 =n; COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). Let T (n) = 2T (n/2) + 5 n; thennlogba =nlog22 =n1 =n; thus f(n) = 5n = Θ(n) = Θ(nlog2 2). COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). Let T (n) = 2T (n/2) + 5 n; thennlogba =nlog22 =n1 =n; thus f(n) = 5n = Θ(n) = Θ(nlog2 2). Thus, condition of case 2 is satisfied; COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 4 T (n/2) + n; then nlogb a = nlog2 4 = n2; thus f(n) = n = O(n2−ε) for any ε < 1. Condition of case 1 is satisfied; thus, T(n) = Θ(n2). Let T (n) = 2T (n/2) + 5 n; thennlogba =nlog22 =n1 =n; thus f(n) = 5n = Θ(n) = Θ(nlog2 2). Thus, condition of case 2 is satisfied; and so, T(n) = Θ(nlog2 2 logn) = Θ(nlogn). COMP3121/3821/9101/9801 10 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also, af(n/b) = 3f(n/4) COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also,af(n/b)=3f(n/4)=3/4n 0.
COMP3121/3821/9101/9801 11 / 22

Master Theorem – Examples
Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also,af(n/b)=3f(n/4)=3/4n 0. This is because for every ε > 0, and every c > 0, no matter how small, log2 n < c · nε for all sufficiently large n. COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also,af(n/b)=3f(n/4)=3/4n 0. This is because for every ε > 0, and every c > 0, no matter how small, log2 n < c · nε for all sufficiently large n. Homework: Prove this. COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also,af(n/b)=3f(n/4)=3/4n 0. This is because for every ε > 0, and every c > 0, no matter how small, log2 n < c · nε for all sufficiently large n. Homework: Prove this. Hint: Use de L’Hˆopital’s Rule to show that log n/nε → 0. COMP3121/3821/9101/9801 11 / 22 Master Theorem - Examples Let T (n) = 3 T (n/4) + n; then nlogb a = nlog4 3 < n0.8; thus f(n) = n = Ω(n0.8+ε) for any ε < 0.2. Also,af(n/b)=3f(n/4)=3/4n 0. This is because for every ε > 0, and every c > 0, no matter how small, log2 n < c · nε for all sufficiently large n. Homework: Prove this. Hint: Use de L’Hˆopital’s Rule to show that log n/nε → 0. Thus, in this case the Master Theorem does not apply! COMP3121/3821/9101/9801 11 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b T (n) = a T + f (n) (1) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b T (n) = a T + f (n) (1) (2) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b2 b3 b2 T (n) = a T + f (n) (1) (2) (3) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., we get T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., we get (1) 􏰇 􏰊􏰉 􏰈 T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 􏰍n􏰎 􏰍 􏰍n􏰎 􏰍n􏰎􏰎 T(n)=aT 􏰉􏰈􏰇􏰊 􏰉 􏰈􏰇 􏰊 +f(n)=a aT +f +f(n) b b2 b (2L) (2R) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., we get (1) 􏰇 􏰊􏰉 􏰈 T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 T(n)=aT 􏰍n􏰎 􏰍 􏰍n􏰎 􏰍n􏰎􏰎 +f(n)=a aT +f +f(n) b b2 b 􏰉􏰈􏰇􏰊 􏰉 􏰈􏰇 􏰊 (2L) (2R) 2 􏰍n􏰎 􏰋n􏰌 =a T b2 +af b +f(n) 􏰉 􏰈􏰇 􏰊 (3L) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., we get (1) 􏰇 􏰊􏰉 􏰈 􏰍n􏰎 􏰍 􏰍n􏰎 􏰍n􏰎􏰎 T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 T(n)=aT 􏰉􏰈􏰇􏰊 􏰉 􏰈􏰇 􏰊 +f(n) 􏰍 n 􏰎􏰎 b2 􏰊 +f(n)=a aT +f b b2 b (2L) 2 􏰍 n 􏰎 (2R) =a T b2 +af +f 􏰈􏰇 􏰋n􏰌 b 2􏰍 +f(n)=a aT 􏰉 􏰍 n 􏰎 b3 +af 􏰋n􏰌 b +f(n) 􏰉 􏰈􏰇 􏰊 (3L) (3R) COMP3121/3821/9101/9801 12 / 22 Master Theorem - Proof: Since 􏰍n􏰎 b implies (by applying it to n/b in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 T =aT +f b b2 b and (by applying (1) to n/b2 in place of n) 􏰍n􏰎 􏰍n􏰎 􏰍n􏰎 and so on ..., we get (1) 􏰇 􏰊􏰉 􏰈 􏰍n􏰎 􏰍 􏰍n􏰎 􏰍n􏰎􏰎 T (n) = a T + f (n) (1) (2) (3) T =aT +f b2 b3 b2 T(n)=aT 􏰉􏰈􏰇􏰊 􏰉 􏰈􏰇 􏰊 +f(n) 􏰍 n 􏰎􏰎 b2 􏰊 +f(n)=a aT +f b b2 b (2L) 2 􏰍 n 􏰎 (2R) =a T b2 +af +f 􏰈􏰇 􏰋n􏰌 b 2􏰍 +f(n)=a aT 􏰉 􏰍 n 􏰎 b3 +af 􏰋n􏰌 b +f(n) 􏰉 􏰈􏰇 􏰊 (3L) 3􏰍n􏰎2􏰃n􏰄􏰋n􏰌 (3R) =aT b3 +af b2 +af b +f(n)=... 􏰉 􏰈􏰇 􏰊 COMP3121/3821/9101/9801 12 / 22 Master Theorem Proof: Continuing in this way logb n − 1 many times we get ... T (n) = a3 T 􏰃 n 􏰄 +a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) = =... b3 b2 b 􏰉 􏰈􏰇 􏰊 COMP3121/3821/9101/9801 13 / 22 Master Theorem Proof: Continuing in this way logb n − 1 many times we get ... T (n) = a3 T 􏰃 n 􏰄 +a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) = b3 b2 b 􏰉 􏰈􏰇 􏰊 =... =a⌊logb n⌋T􏰃 n 􏰄+a⌊logb n⌋−1f􏰃 n 􏰄+... b⌊logb n⌋−1 b⌊logb n⌋ + a3 f 􏰃 n 􏰄 + a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) b3 b2 b COMP3121/3821/9101/9801 13 / 22 Master Theorem Proof: Continuing in this way logb n − 1 many times we get ... T (n) = a3 T 􏰃 n 􏰄 +a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) = b3 b2 b 􏰉 􏰈􏰇 􏰊 =... =a⌊logb n⌋T􏰃 n 􏰄+a⌊logb n⌋−1f􏰃 n 􏰄+... b⌊logb n⌋−1 b⌊logb n⌋ + a3 f 􏰃 n 􏰄 + a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) b3 b2 b ⌊log n⌋−1 􏰃n􏰄b 􏰃n􏰄 ≈alogbnT + 􏰂 aif blogb n i=0 bi COMP3121/3821/9101/9801 13 / 22 Master Theorem Proof: Continuing in this way logb n − 1 many times we get ... T (n) = a3 T 􏰃 n 􏰄 +a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) = b3 b2 b 􏰉 􏰈􏰇 􏰊 =... =a⌊logb n⌋T􏰃 n 􏰄+a⌊logb n⌋−1f􏰃 n 􏰄+... b⌊logb n⌋−1 b⌊logb n⌋ + a3 f 􏰃 n 􏰄 + a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) b3 b2 b ⌊log n⌋−1 ≈alogbnT blogb n We now use alogb n = nlogb a: T(n)≈nlogbaT(1)+ 􏰂 aif bi i=0 􏰃n􏰄b 􏰃n􏰄 + 􏰂 aif i=0 bi ⌊log n⌋−1 b 􏰃n􏰄 (4) COMP3121/3821/9101/9801 13 / 22 Master Theorem Proof: Continuing in this way logb n − 1 many times we get ... T (n) = a3 T 􏰃 n 􏰄 +a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) = b3 b2 b 􏰉 􏰈􏰇 􏰊 =... =a⌊logb n⌋T􏰃 n 􏰄+a⌊logb n⌋−1f􏰃 n 􏰄+... b⌊logb n⌋−1 b⌊logb n⌋ + a3 f 􏰃 n 􏰄 + a2 f 􏰃 n 􏰄 + a f 􏰃 n 􏰄 + f (n) b3 b2 b ⌊log n⌋−1 ≈alogbnT blogb n We now use alogb n = nlogb a: T(n)≈nlogbaT(1)+ 􏰂 aif bi i=0 Note that so far we did not use any assumptions on f (n) . . . COMP3121/3821/9101/9801 􏰃n􏰄b 􏰃n􏰄 + 􏰂 aif i=0 bi ⌊log n⌋−1 b 􏰃n􏰄 (4) 13 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 Case 1: f(m) = O(mlogb a−ε) ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε i=0 bi bi i=0 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε bi i=0 =O 􏰂ainlogba−ε bi  i=0 ⌊log n⌋−1 b􏰃􏰄  bi  i=0 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε bi bi i=0 =O a =Onb bi i=0 i=0 i=0 b􏰃􏰄bi ⌊log n⌋−1 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε   ⌊log n⌋−1􏰍 􏰎  COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε i=0 bi bi =O a =Onb  ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 i=0 b􏰃􏰄bi ⌊log n⌋−1 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε   ⌊log n⌋−1􏰍 􏰎 i=0 bi i=0  =Onloga−ε 􏰂  i ⌊log n⌋−1 b 􏰃a􏰄 b blogb a−ε i=0 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε bi bi i=0 ⌊log n⌋−1 =O a =Onb ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 i=0 b􏰃􏰄bi   ⌊log n⌋−1􏰍 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε 􏰎  i=0  log a−ε =On b bi ⌊log n⌋−1 i=0 􏰂 b 􏰃a􏰄  ⌊log n⌋−1 􏰂 i i=0 blogb a−ε i=0 blogb ab−ε i log a−ε b 􏰃a􏰄  =On b   COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε bi bi i=0 ⌊log n⌋−1 =O a =Onb ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) i=0 b􏰃􏰄bi   ⌊log n⌋−1􏰍 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε 􏰎  i=0  log a−ε =On b bi ⌊log n⌋−1 i=0 􏰂 b 􏰃a􏰄  ⌊log n⌋−1 􏰂 i i log a−ε b 􏰃a􏰄  =On b    =Onloga−ε 􏰂 blogb a−ε ⌊logb n⌋−1 􏰍abε 􏰎i blogb ab−ε i=0 i=0 b a i=0 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε bi bi i=0 ⌊log n⌋−1 =O a =Onb ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) i=0 b􏰃􏰄bi   ⌊log n⌋−1􏰍 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε 􏰎  i=0  log a−ε =On b bi ⌊log n⌋−1 i=0 􏰂 b 􏰃a􏰄  ⌊log n⌋−1 􏰂 i  bb i=0 i=0 ⌊logb n⌋−1 􏰍abε 􏰎i a i log a−ε b 􏰃a􏰄  =On b   blogb a−ε i=0 blogb ab−ε ⌊logb n⌋−1   =O nlog a−ε 􏰂 =O nlog a−ε 􏰂 (bε)i i=0 COMP3121/3821/9101/9801 14 / 22 T(n)≈nlogbaT(1)+ 􏰂 aif􏰃 􏰄 ⌊logb n⌋−1 n bi i=0 􏰉 􏰈􏰇 􏰊 Case 1: f(m) = O(mlogb a−ε) ⌊log n⌋−1 ⌊log n⌋−1 b􏰃􏰄b􏰃􏰄 􏰂 aif n = 􏰂 aiO n logba−ε i=0  log a−ε =On b bi ⌊log n⌋−1 i=0 bi bi i=0 ⌊log n⌋−1 =O a =Onb i=0 b􏰃􏰄bi   ⌊log n⌋−1􏰍 􏰂 i nlogba−ε loga−ε 􏰂 a (bi)logb a−ε 􏰎  􏰂 b 􏰃a􏰄  ⌊log n⌋−1 􏰂 i i log a−ε b 􏰃a􏰄  =On b   = O 􏰏 nlogb a−ε ; we are using m􏰂−1 qm −1 q − 1 blogb a−ε i=0 blogb ab−ε ⌊logb n⌋−1   =O nlog a−ε 􏰂 =O nlog a−ε 􏰂 (bε)i  bb ⌊logb n⌋−1 􏰍abε 􏰎i a (bε)⌊logb n⌋ −1􏰐 i=0 qi = i=0 i=0 bε − 1 COMP3121/3821/9101/9801 i=0 14 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰏 =O nlogba−ε (bε)⌊log n⌋−1 bε − 1 􏰐 􏰂 aif i=0 b bi COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰏 􏰐 (bε)⌊log n⌋−1 =O nlogba−ε b bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰂 aif i=0 bi COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰏 􏰐 (bε)⌊log n⌋−1 =O nlogba−ε b bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰍log a−εnε−1􏰎 bε − 1 􏰂 aif i=0 bi =Onb COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰏 􏰐 (bε)⌊log n⌋−1 =O nlogba−ε b bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰍log a−εnε−1􏰎 bε − 1 􏰍 nlogb a − nlogb a−ε 􏰎 􏰂 aif i=0 bi =Onb =O bε − 1 COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰂 aif i=0 􏰏 􏰐 􏰃n􏰄 (bε)⌊log n⌋−1 =O nlogba−ε b bi bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰍log a−εnε−1􏰎 bε − 1 􏰍 nlogb a − nlogb a−ε 􏰎 =Onb =O = O 􏰃nlogb a􏰄 bε − 1 COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰂 aif i=0 bi 􏰏 􏰐 (bε)⌊log n⌋−1 =O nlogba−ε b bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰍log a−εnε−1􏰎 bε − 1 􏰍 nlogb a − nlogb a−ε 􏰎 =O = O 􏰃nlogb a􏰄 T(n) ≈ nlogb aT (1) + =Onb Since we had: 􏰂 aif i=0 bi we get: bε − 1 ⌊log n⌋−1 b 􏰃n􏰄 COMP3121/3821/9101/9801 15 / 22 Master Theorem Proof: Case 1 - continued: ⌊log n⌋−1 b 􏰃n􏰄 􏰏 􏰐 (bε)⌊log n⌋−1 =O nlogba−ε b bε − 1  􏰃b⌊logb n⌋􏰄ε −1 =O nlog a−ε b bε − 1 􏰍log a−εnε−1􏰎 bε − 1 􏰍 nlogb a − nlogb a−ε 􏰎 Since we had: T(n) ≈ nlogb aT (1) + T(n) ≈ nlogb aT (1) + O 􏰃nlogb a􏰄 = Θ􏰃nlogb a􏰄 COMP3121/3821/9101/9801 we get: 􏰂 aif i=0 bi =Onb =O = O 􏰃nlogb a􏰄 bε − 1 ⌊log n⌋−1 b 􏰃n􏰄 􏰂 aif i=0 bi 15 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga i=0 afbi = aΘbi i=0 COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga afbi = aΘbi i=0 i=0 ⌊log n⌋−1  b 􏰃n􏰄b =Θ􏰂ai loga  bi  i=0 COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga afbi = aΘbi i=0 i=0 ⌊log n⌋−1  b 􏰃n􏰄b =Θ􏰂ai loga  bi  i=0  =Θnloga 􏰂 ⌊logb n⌋−1 􏰍 ai 􏰎 b i=0 (bi)logb a COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga afbi = aΘbi i=0 i=0 ⌊log n⌋−1  b 􏰃n􏰄b =Θ􏰂ai loga  bi  i=0  =Θnloga 􏰂 ⌊logb n⌋−1 􏰍 ai 􏰎 b i=0 (bi)logb a  ⌊log n⌋−1  b 􏰃a􏰄 =Θnloga 􏰂 i b blogb a i=0 COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga afbi = aΘbi i=0 i=0 ⌊log n⌋−1  b 􏰃n􏰄b =Θ􏰂ai loga  bi  i=0  =Θnloga 􏰂 ⌊logb n⌋−1 􏰍 ai 􏰎 b i=0 (bi)logb a  ⌊log n⌋−1  b 􏰃a􏰄 =Θnloga 􏰂 i b blogb a i=0  ⌊logbn⌋−1  = Θ nlogb a 􏰂 1 i=0 COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2: f(m) = Θ(mlogb a) ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b 􏰃n􏰄b 􏰂i 􏰂iloga afbi = aΘbi i=0 i=0 ⌊log n⌋−1  b 􏰃n􏰄b =Θ􏰂ai loga  bi  i=0  =Θnloga 􏰂 ⌊logb n⌋−1 􏰍 ai 􏰎 b i=0 (bi)logb a  ⌊log n⌋−1  b 􏰃a􏰄 =Θnloga 􏰂 i b blogb a i=0  ⌊logbn⌋−1  = Θ nlogb a 􏰂 1 i=0 = Θ􏰃nlogb a⌊logb n⌋􏰄 COMP3121/3821/9101/9801 16 / 22 Master Theorem Proof: Case 2 (continued): Thus, ⌊log n⌋−1 b􏰃n􏰄􏰃􏰄􏰃􏰄 􏰂 aif bi =Θ nlogbalogbn =Θ nlogbalog2n i=0 COMP3121/3821/9101/9801 17 / 22 Master Theorem Proof: Case 2 (continued): Thus, ⌊log n⌋−1 b􏰃n􏰄􏰃􏰄􏰃􏰄 􏰂 aif bi =Θ nlogbalogbn =Θ nlogbalog2n i=0 because logb n = log2 n · logb 2 = Θ(log2 n). Since we had (1): ⌊log n⌋−1 T(n) ≈ nlogb aT (1) + 􏰂 aif i=0 b 􏰃n􏰄 bi COMP3121/3821/9101/9801 17 / 22 Master Theorem Proof: Case 2 (continued): Thus, we get: ⌊log n⌋−1 b􏰃n􏰄􏰃􏰄􏰃􏰄 􏰂 aif bi =Θ nlogbalogbn =Θ nlogbalog2n i=0 because logb n = log2 n · logb 2 = Θ(log2 n). Since we had (1): ⌊log n⌋−1 T(n) ≈ nlogb aT (1) + T(n) ≈ nlogb aT (1) + Θ􏰃nlogb a log2 n􏰄 = Θ 􏰃nlogb a log2 n􏰄 b 􏰃n􏰄 􏰂 aif i=0 bi COMP3121/3821/9101/9801 17 / 22 Master Theorem Proof: Case 3: f(m) = Ω(mlogb a+ε) and af(n/b) ≤ cf(n) for some 0 < c < 1. We get by substitution: f(n/b) ≤ c f(n) a f(n/b2) ≤ c f(n/b) a f(n/b3) ≤ c f(n/b2) a ... f(n/bi) ≤ c f(n/bi−1) a COMP3121/3821/9101/9801 18 / 22 Master Theorem Proof: Case 3: f(m) = Ω(mlogb a+ε) and af(n/b) ≤ cf(n) for some 0 < c < 1. We get by substitution: f(n/b) ≤ c f(n) a f(n/b2) ≤ c f(n/b) a f(n/b3) ≤ c f(n/b2) a ... f(n/bi) ≤ c f(n/bi−1) a By chaining these inequalities we get 2 c cc c2 f(n/b )≤ f(n/b)≤ · f(n)= 2 f(n) ... a􏰉􏰈􏰇􏰊aa a 􏰉 􏰈􏰇 􏰊 3c2cc2 c3 f(n/b )≤ f(n/b )≤ · 2 f(n)= 3 f(n) a􏰉 􏰈􏰇 􏰊 a a a 􏰉 􏰈􏰇 􏰊 ici−1cci−1 ci f(n/b)≤ f(n/b )≤ · i−1 f(n)= i f(n) a􏰉 􏰈􏰇 􏰊 a a a 􏰉 􏰈􏰇 􏰊 COMP3121/3821/9101/9801 18 / 22 Master Theorem Proof: Case 3 (continued): i ci We got f(n/b ) ≤ ai f(n) COMP3121/3821/9101/9801 19 / 22 Master Theorem Proof: Case 3 (continued): i ci We got f(n/b ) ≤ ai f(n) Thus, ⌊log n⌋−1 ⌊log n⌋−1 b 􏰃n􏰄b ci ∞ f(n) bi ai 1−c 􏰂 aif ≤ 􏰂 ai i=0 i=0 i=0 f(n) f(n) COMP3121/3821/9101/9801
f(n) bi ai 1−c
⌊log n⌋−1
b 􏰃n􏰄
19 / 22

Master Theorem Proof:
Case 3 (continued):
i ci
We got f(n/b ) ≤ ai f(n)
Thus,
i=0 Since we had (1):
⌊log n⌋−1 ⌊log n⌋−1
b 􏰃n􏰄b ci
∞
􏰂
aif
≤ 􏰂 ai i=0
f(n) f(n)
T(n) = Θ(f(n)) COMP3121/3821/9101/9801
f(n) bi ai 1−c
⌊log n⌋−1
b 􏰃n􏰄
19 / 22

Master Theorem Proof: Homework
Exercise 1: Show that condition
f(n) = Ω(nlogb a+ε)
follows from the condition
af(n/b)≤cf(n) forsome0

Related Posts