HW2 solution
4.2-3
How would you modify Strassen’s algorithm to multiply n*n matrices in which n
is not an exact power of 2? Show that the resulting algorithm runs in time
Suppose <n<N=
We could extend original n*n matrices to N*N matrices by appending zeros.
Then the Strassen’s algorithm could work on extended matrices. Finally,
eliminating the appended elements in the matrices needs O( ).
Since < n, it follows that N < 2n. Therefore, the runtime becomes
( ) ( )
4.3-2
Show that the solution of T (n) = T(⌈ ⌉) + 1 is O( lgn )
We will use substitution method to verify the given solution. We start by trying
to prove that T (n) ≦ clg(n).
T (n) ≦ clg(⌈ ⌉) + 1
< clg(n/2 + 1) + 1
= clg( )+1
= clg(n + 2) - c + 1
This is inconclusive, so we will modify the solution a bit. We will try to prove
that T (n) ≦clg(n - b). Note that this still would imply that T (n) is O(lgn).
T (n) ≦ clg(⌈ ⌉ )+1
< clg(n/2- b + 1) + 1
= clg( )+1
= clg(n - b - (b - 2)) - clg2 + 1
≦clg(n - b)
The last inequality is true if b ≧ 2 and c ≧ 1. Note that this still does not work
for n = 1 as it involves computing clog(1-2). It also does not work for n = 2. So
the simple solution is to move up the base case.
4.3-6
Show that the solution to T(n) = 2T( n / 2 17 ) + n is O( nlgn )
Let us assume that it holds ∀ m ≤⌊ ⌋
So, T(m) ≤ cm lg m ∀ m ≤⌊ ⌋
Hence we can write
T(n) = 2T( ⌊ ⌋)+n
≤ 2c ( ⌊ ⌋ )lg ( ⌊ ⌋)+n
≤ 2c (n/2+17)lg(n/2 +17) + n
≤ 2c(n/2+17) lg(n/2+n/4) + n ∀ n/4 ≥ 17
= (cn + 34c) lg(3n/4) + n
= cn lgn – cn lg 4/3 + 34c lg n – 34c lg 4/3 + n
≤ cn lgn – cn lg 4/3 + 34c lg n + n
As lg n = 0(n) therefore 34 c lgn ≤ kn ∀ n ≥ no hence
T(n) ≤ cn lg n + n(1- c lg 4/3) + kn ∀ n ≥ max {n0 , 68}
= cn lg n + n(k+1-c lg 4/3)
now we can always choose c such that
k+1 – c lg 4/3 ≤ 0
k+1 ≤ c lg 4/3
c ≥ (k+1)/ lg(4/3) = k
T(n) ≤ cn lg n
for some constant c ≥ k and n ≥ max {n0, 68}………….(Hence proved)
4.4-5
Use a recursion tree to determine a good asymptotic upper bound on the
recurrence . Use the substitution method to
verify your answer.
Let , and we could know that
∑
∑ ∑
Assume is integer division, for even n, so the first
sum consists of two equal halves :
Since for every
Since
Let’s consider this for only , since T is monotonous: and
since
Let
Therefore, we could get that
4.5-1
Use the master method to give tight asymptotic bounds for the following
recurrences.
b. T(n) = 2T(n/4)+√
case2:
T(n) = aT(n/b)+f(n)
If f(n) = θ( o ba
) thenT(n) =θ( o ba
𝑙𝑔 )
a = 2, b = 4, f (n) =√
o 4
= = f(n)
So , T(n) = θ(√ 𝑙𝑔 )
4-3
Give asymptotic upper and lower bounds for T(n) in each of the following
recurrences.Assume that T(n) is constant for sufficiently small n. Make your
bounds as tight as possible, and justify your answers.
b.
Solution 1
Let
Then the equation can be transformed
𝑔
𝑔
∑ // harmonic sum
Thus
Solution 2
……
When the first term reduces to o
, so we have
o
∑
o
∑
o
∑
∑o
This is the harmonic sum, so we have
d.
assume
T(n) = 3T(n/3 - 2)+ n/2
≤ 3c(n/3 - 2) lg(n/3 - 2) + n/2
≤ 3c(n/3) lg(n/3) + n/2
= cn lg(n/3) + n/2
= cnlg(n) – cnlg(3) + n/2
≤ cnlg(n) ---------- for
So the upper bound is
assume
T(n) = 3T(n/3 - 2)+ n/2
≥ 3c(n/3 - 2) lg(n/3 - 2) + n/2
≥ 3c(n/3 - 2) lg(n/3 – n/6) + n/2 for n ≥ 12
= (cn – 6c) lg(n/6) + n/2
= cnlgn – cnlg6 – 6clgn + 6clg6 + n/2
≥ cnlgn – cnlg6 – 6clgn + n/2
As lg n = (n) therefore 6clgn ≤ kn ∀ n ≥ hence
T(n) ≥ cnlgn + n(1/2 - clg6) – kn
= cnlgn + n(1/2 - clg6 – k)
now we can always choose c such that
1/2 - clg6 – k ≤ 0
1/2 – k ≤ clg6
c ≥ 1/(2lg6) – k/lg6 ------ we choose c = 1/(2lg6)
T(n) ≥ cn lg n
Therefore, the time complexity is
