1

I'm really stuck on this recurrence problem. $T(1) = 1$ in this case or for any small constant

T(n) = 2T(n/2) + n/log(n) + n

= 2(2T(n/4) + n/2/log(n/2)) + n/log(n) + n/2 + n

= 4T(n/4) + n/log(n/2) + n/log(n) + n/2 + n/4 + n

= 8T(n/8) + n/log(n/4) + n/log(n/2) + n/2 + n/4 + n/6 + n

= 16T(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n) + n/8 + n/4 + n/2 + n

For the most part I believe I expanded it out correctly, now I'm lost as to what the relation is. Now I believe I plug in $2^{k}$ for each n value and find some form of pattern. However I am lost as to what this pattern would look like. My best guess is $T(1) = 1$ therefore $1 + \sum \frac{2^{k}}{\log(2^{k}/2)} + 2^{k}$

rtybase
  • 16,907
skryt
  • 63
  • 8
  • Unless there is a way to simplify (n/lgn) + n where I can use the master theorem. – skryt Oct 10 '17 at 20:24
  • 1
    You have quite a few mistakes in your expansion, could you fix them please? It makes editing quite difficult, you should have some latex examples too ... – rtybase Oct 10 '17 at 21:18
  • For example the 2nd line $2\left(2T\left(\frac{n}{4}\right) + \frac{n/2}{\log(n/2)}\right) + \frac{n}{\log(n)} + \frac{n}{2} + n$, where is $\frac{n}{2}$ (the one outside the brackets) coming from? You multiply the content of the brackets by $2$ so it must be $n$. – rtybase Oct 10 '17 at 21:23
  • Assuming you need an asymptotic expression, then you want the master theorem here: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms) – Steven Stadnicki Oct 10 '17 at 21:47

0 Answers0