2
$\begingroup$

I am trying to find the time complexity for the recurrence $T(n) = 2T(n^{1/2}) + \log n$. I am pretty close to the solution, however, I have run into a roadblock. I need to solve $n^{{1/2}^k} = 1$ for $k$ to simplify my substitution pattern. I am not looking for answers to the recurrence, just a solution for $k$. Any help would be appreciated. Thanks

  • 1
    You do not want $n^{1/2^k}$ to be $1$ to solve the recurrence. You just need $n^{1/2^k}$ small i.e. $\mathcal{O}(1)$ so that $T(\mathcal{O}(1)) = \mathcal{O}(1)$.2012-10-27

2 Answers 2

1

You do not want $n^{1/2^k}$ to be $1$ to solve the recurrence. You just need $n^{1/2^k}$ small i.e. $\mathcal{O}(1)$ so that $T(\mathcal{O}(1)) = \mathcal{O}(1)$. To solve the recurrence, proceed as follows. $T(n) = 2 T(n^{1/2}) + \log n$ Setting $n = x^{2^{m}}$, we get that $T(x^{2^m}) = 2 T(\sqrt{x^{2^m}}) + 2^m \log (x) = 2T(x^{2^m/2}) + 2^m \log (x) = 2T(x^{2^{m-1}}) + 2^m \log (x)$ Denoting $T(x^{2^m}) = g_x(m)$, we then get \begin{align} g_x(m) & = 2g_x(m-1) + 2^m \log(x) = 2(2g_x(m-2) + 2^{m-1} \log(x)) + 2^m \log(x)\\ & = 4g_x(m-2) + 2^m \log(x) + 2^m \log(x)\\ & = 8g_x(m-3) + 2^m \log(x) + 2^m \log(x) + 2^m \log(x)\\ & = 2^mg_x(0) + \underbrace{2^m \log(x) + 2^m \log(x) + 2^m \log(x) + \cdots 2^m \log(x)}_{m \text{ such terms}}\\ & = 2^mg_x(0) + m2^m \log(x) \end{align} $T(n) = T(x) \dfrac{\log n}{\log x} + m \log n = T(x) \dfrac{\log n}{\log x} + \left(\dfrac{\log \log n - \log \log x}{\log 2}\right) \log n$ Hence, $T(n) = \mathcal{O}(\log n \times \log \log n)$

0

The non-symbolic way to think of it is that $k$ is the number of times you can take the square root of $n$ before you get to a constant (let's say 2 to make things easier later). So it is the inverse of how many times it takes to square 2 before you get (around) to your number $n$.

$2, 4, 16, 256, 65536, 4G,...$ or $2^{2^k}$.

'$\log$' doesn't work, that's only for multiples of 2, not squaring.

'$\log^{*}$' also doesn't work, that's only for towers of 2, $2^{2^{2^ .\ ^2}}$, not squaring.

How do you get $k$ from $n = 2^{2^k}$. Just take log twice.

$\log 2^{2^k} = 2^k$

so

$\log \log 2^{2^k} = k$

Now that is the depth of your tree, and you can add up all the $\log n$ parts at each node to get the solution.