retagged by
1,102 views
0 votes
0 votes

T(n) = 2n T $(\frac{n}{2})$ + nn

retagged by

3 Answers

1 votes
1 votes

Here r d steps though I m getting a different answer. 

I've solved dis equation using d Master's Theorem. You can verify d descp. Yeah. :)

Give equation is of d form:

aT(n/b)+f(n)

Here given equation is:

2n(n/2)+nn.

So a=2n, b=2, f(n)=nn

Now a=2n, b=2

Keeping it in logba, we have log22,

So we get nlog22 which equals n, since(log22=1). 

Now nthru d form nlogba

So nlogba  is equal to d case II of Master's Theorem. 

So T(n) time complexity is given by 

T(n)=θ(nlog2n)

is d final answer. :)

0 votes
0 votes
Is it O(2^(n^(log2(n)-1)) ?? Or it is near to the answer ??
edited by
0 votes
0 votes
Solve it by using recursive tree method.. You will get n^n cost at each level and tree grows upto logn therefore O(n^n logn)

Related questions

1 votes
1 votes
1 answer
1
3 votes
3 votes
4 answers
4
LavTheRawkstar asked Apr 16, 2017
4,384 views
T(n) = 100 T (n/99) + log(n!) Answer is T(n) = θ (n log n)a)answer is justifiedb)answer is not justifiedc)cannot be determinedd)none