Question

Show that the solution of T(n) = 2T( ën/2û ) + n is W(n lg n)....

Show that the solution of T(n) = 2T( ën/2û ) + n is W(n lg n). Conclude that the solution is Q(n lg n).

Homework Answers

Answer #1

Solution for the problem is provided below, please comment if any doubts:

Here we need to prove that the solution of T(n) = 2T( n/2) + n is O(n lg n)

We can prove this using substitution method,

For T(n)=O(n lg n), there must exists a constant “c” such that T(n) ≤ c (n lg n)

Induction hypothesis is assume that “T(n) ≤ c (n lg n)” all numbers less than n

Now, T((n/2)) ≤ 2c (n/2) lg (n/2)+n

       ≤ cn lg (n/2)+n = cn ( lg n – lg 2)+n = cn ( lg n – 1)+n

            =cn lg n – cn +n

cn lg n – cn +n ≤ cn lg n, for c>1

That is for c>1 T(n) ≤ c (n lg n)

That is T(n)=O(n lg n)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Find the runtime complexity for the function defined recursively by T(n) = 2T(squareroot(n) + lg n
Find the runtime complexity for the function defined recursively by T(n) = 2T(squareroot(n) + lg n
(Subject: Data Structures and Algorithms) (Q) Let $T(n)=T(n/4)+T(3n/4)+n$ and $T(n)= T(n/5)+T(4n/5)+n$. The former has a solution...
(Subject: Data Structures and Algorithms) (Q) Let $T(n)=T(n/4)+T(3n/4)+n$ and $T(n)= T(n/5)+T(4n/5)+n$. The former has a solution $T(n) = c n \lg{n}$ and the latter a $T(n) =d n \lg{n}$, for some constant $c,d$. Which of the $c,d$ is larger? No justification needed. Just choose the best suitable answer. (Options) (i) $c$ is larger (ii) $d$ is larger (iii) $c=d$
Algorithm problem 3 [BvG1.5] Show that [lg(n+ 1)] =[lg n] + 1 for integers n≥1. Hint:...
Algorithm problem 3 [BvG1.5] Show that [lg(n+ 1)] =[lg n] + 1 for integers n≥1. Hint: Group values of n into ranges of the form (2^(k)) ≤ n < (2^(k+1))
Consider W = Span{p1(t),p2(t)} where p1(t) = 1−t^2 and p2(t) = 3+2t are the polynomials defined...
Consider W = Span{p1(t),p2(t)} where p1(t) = 1−t^2 and p2(t) = 3+2t are the polynomials defined on the interval [−1,1]. Find the orthogonal projection of q(t) = t^2−t−1 onto W.
P(W < t) = 1/12(t^2+ 2t^3) for 0 ≤ t ≤ 2. Write an integral for...
P(W < t) = 1/12(t^2+ 2t^3) for 0 ≤ t ≤ 2. Write an integral for E[√(W+ 3) ].
Please show all work. A spring has natural frequency w=2. An external force f(t)=3cos(2t) is applied...
Please show all work. A spring has natural frequency w=2. An external force f(t)=3cos(2t) is applied to the spring. Its initial displacement is 1 and initial velocity is 2. Find the displacement of the spring y(t) at any time t. What happens to the spring in the long run?
Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Solve the Recurrence Relation T(n) = 2T(n/3) + 2, T(1) = 1
Find a Particular Solution of y'''-4y'=t+3cos(t)+e-2t
Find a Particular Solution of y'''-4y'=t+3cos(t)+e-2t
Differential equation for y'=2y-t+g(y) that has a solution y(t)=e^(2t)
Differential equation for y'=2y-t+g(y) that has a solution y(t)=e^(2t)
1. Show that |z − w| ≤ |z − t| + |t − w| for all...
1. Show that |z − w| ≤ |z − t| + |t − w| for all z, w, t ∈ C. 2.Does every complex number have a multiplicative inverse? Explain 3.Give a geometric interpretation of the expression |z − w|, z, w ∈ C. 4.Give a lower bound for |z + w|. Show your result. 5.Explain how to compute the inverse of a nonzero complex number z geometrically. 6.Explain how to compute the conjugate of a complex number z geometrically....
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT