0

I tried to unwinding the recursive function, but I got a

$T(n) = 1 + (\log(1))^2 + (\log(2))^2 + ... + (\log(n-1))^2 + (\log(n))^2$

How can I simplify it, or can I get time complexity from other way?

J.G.
  • 115,835
Julie Guo
  • 11
  • 2
    Hint: $T(n) = 1+\sum_{i=1}^n \log^2(i)$, which is awfully similar to $1+\int_{1}^n \log^2(x)dx$. – Kolja Aug 15 '22 at 06:50
  • You won't get an exact closed form. But luckily, "complexity" only requires you to get a result of the form $T(n)\in\Theta(f(n))$. – J.G. Aug 15 '22 at 06:58
  • Hi Kolja, I did some calculation, the integration is equal to x(logx)^2 - 2xlogx + 2x + C, so my answer should be O(n(logn)^2)? can you please have a look, Is my thought correct? – Julie Guo Aug 15 '22 at 07:23

0 Answers0