retagged by
289 views

1 Answer

1 votes
1 votes
$T(n) = T(n-2) + 2log n$ ---- (1)

$T(1) = 1$

Putting n = 3  in (1),

$T(3) = T(1) + 2log 3$

or $T(3) = 1 + 2 log 3$

Similarly we get,

$T(5) = 1 + 2log3 + 2 log5 = 1 + 2(log 3+ log 5)$

$T(7) = 1 + 2(log 3 + log 5) + 2log 7 =1+2(log 3 + log 5 + log 7)$

Therefore,

$T(n) = 1 + 2(log 3 + log 5 + log 7... + log n)$

$T(n) = 1 + 2(log 3.5.7..n)$             //log a+log b = log (a.b)

So, $T(n)< log n^n$      //check by putting values for n

which is $O(nlogn)$.

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,250 views
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
0 votes
0 votes
0 answers
4
garvit_vijai asked Nov 17, 2018
448 views
How to solve the following recurrence relation?T(n) = T(n-6) + n2 , n>7T(n) = 1 , n<= 7