retagged by
13,285 views

3 Answers

1 votes
1 votes

yes we can convert it in master theorem

T(n)=64 T(n/8) - n2log n

       =64 T(n/8) + n2log n-1

       =64 T(n/8) + n2log (1/n)

     here nlogba = n log864 = n2

now,  n2log(1/n) > n2

Then complexity will be O( n2log 1/n)

edited by
0 votes
0 votes

$\begin{align*} T(n) &= 64\ T(n/8) - n^2 \log n\\ &= 64\ T(n/8) + n^2 \log \frac{1}{n}\\ \end{align*}$

this does not satisfy the generic form of master method. It is close to the case of Master Method, where :

but fails so do other cases too. So, one of the method to do this is Akra–Bazzi Method.

here, 
we need to choose $p$ such that $\sum_{i=1}^{k} {a_ib_i^p}=1$
$64 \left( \frac{1}{8} \right )^p = 1 \\ \text{satisfies for p = 2}$ and also, $\left| \mathrm{g'(x)} \right| \leq \mathrm{x}^c \qquad \text{for some } c \in \mathbb{R}$

so, 
$\begin{align*} T(x) &= \Theta\left( x^p + x^p \int_{1}^{x} \frac{u^2 \log \frac{1}{u}}{u^{p+1}}\ du \right )\\ &= \Theta\left( x^2 - x^2 \int_{1}^{x} \frac{u^2 \log {u}}{u^{3}}\ du \right )\\ &= \Theta\left( x^2 - x^2 \int_{0}^{\log x} t\ dt \right )\\ &= \Theta\left( x^2 - \frac{x^2}{2} \{\log x\}^2 \right )\\ &= \Theta\left( x^2 + \frac{x^2}{2} \log x\ .\ \log \frac{1}{x} \right )\\ &= \Theta\left( \frac{x^2}{2}\ \log \frac{1}{x}\ \log x \right )\\ \\ T(n) &= \Theta\left( \frac{n^2}{2}\ \log \frac{1}{n}\ \log n \right )\\ \end{align*}$

edited by
0 votes
0 votes
YES we can’t predict complexity because no algorithm has negative workdone or negative time taken by algorithm. So it is hard to find TC  of negative f(n)

Related questions

9 votes
9 votes
1 answer
1
anoop yadav 2 asked Jan 8, 2018
13,326 views
How to solve above recurrence relation (With substitution method)??
7 votes
7 votes
3 answers
2
bts asked May 29, 2018
1,832 views
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }