Finding an Exact Solution for the Recurrence Formula f(n) = 2f(sqrt(n)) + n

[alyafey22]

Hello MHB

Solve the following recurrence formula

$$f(n) = 2f(\sqrt{n}) + n$$

I was able to find a bound for the function but no success in finding an exact solution. Any ideas ?

 

[Nono713]

I don't think there is an easy expression for it. Using structural induction you can easily prove that the following holds for all $k \in \mathbb{N}$:
$$f(n) = 2^k f \left ( n^{2^{-k}} \right ) + \sum_{i = 0}^{k - 1} 2^i n^{2^{-i}} \tag{$\star$}$$
Now if we assume that $f(n) = c$ for all $n \leq 2$ (otherwise the recurrence does not converge) we can plug in $k = \lceil \log_2{\log_2{n}} \rceil$ to get:
$$f(n) = c 2^{\lceil \log_2{\log_2{n}} \rceil} + \sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} 2^i n^{2^{-i}} = c' \log_2{n} + \sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} 2^i n^{2^{-i}}$$
For $n > 2$ and with $c \leq c' < 2c$ depending on how close $\log_2 \log_2 n$ is to its ceiling. Unfortunately the sum does not seem to have a simple exact expression. However it is quite easy to see that the $2^i$ factor is upper-bounded by $\log_2{n}$, so that we have:
$$\sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} 2^i n^{2^{-i}} \leq \log_2{n} \sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} n^{2^{-i}}$$
Furthermore $n^{2^{-i}} \leq 1 + 2^{-i} n$ for all $i \geq 0$, so that:
$$\sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} n^{2^{-i}} \leq \sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} \left ( 1 + 2^{-i} n \right ) = \lceil \log_2{\log_2{n}} \rceil + n \sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} 2^{-i} \leq \lceil \log_2{\log_2{n}} \rceil + 2n$$
Which gives us:
$$\sum_{i = 0}^{\lceil \log_2{\log_2{n}} \rceil - 1} 2^i n^{2^{-i}} \leq 2n \log_2 n + \log_2 n \lceil \log_2{\log_2{n}} \rceil$$
Or, putting everything together:
$$f(n) \leq \left ( 2n + c' \right ) \log_2 n + \log_2 n \lceil \log_2{\log_2{n}} \rceil \in O \left ( n \log{n} \right )$$
Of course, it does grow slower than that as the ratio of $f(n)$ to its approximation tends to zero but I don't know how to obtain a tighter bound. (did you find a better one?) In any case, I don't know how to find an exact solution either, and I doubt a simple expression for it exists :(
​

 

[alyafey22]

Assume that $n$ is a power of 2 then use the change of variable $n = 2^k $

$$f(2^k) = 2f(2^{k/2})+2^k $$

Now let $g(k) = f(2^k)$ so we have

$$g(k)= 2g\left( \frac{k}{2}\right)+2^k $$

Now if we use the Master theorem we get

$$g(k) = \Theta(2^k)$$

which implies that

$$f(n) = \Theta(n)$$

 

[Nono713]

Very sleek! I wonder if an exact solution exists now..

 

[jacobi1]

While all the other conditions of Case 3 of the Master Theorem hold, I don’t believe that the regularity condition,
$$ 2 \times 2^{k/2} \leq d \times 2^k, \ d < 1, \ k > N, $$
holds.
This holds for $ k \geq 2 \left (1-\log_{2} d \right ) $, but I don’t know…I’d like to have a numerical value for d that doesn’t depend on k. Maybe I’m wrong.
Anyway, I have a possible solution.
Starting from $ f(n) = 2 f(\sqrt n ) +n $, make the substitution $ n = 2^{2^k} $. The equation then becomes
$$ f \left ( 2^{2^k} \right ) = 2 f \left ( 2^{2^{k-1}} \right ) + 2^{2^k}. $$
Substituting $ g(k) = f \left ( 2^{2^k} \right ), $ the equation becomes
$$ g(k) = 2 g(k-1) +2^{2^k}. $$
Iterating, we see that
$$ g(k) = 4 g(k-2) + 3 \times 2^{2^k} = 8 g(k-3) + 7 \times 2^{2^k} = … $$
We see that
$$ g(k) = 2^c g(k-c) +\left ( 2^{c} -1 \right ) 2^{2^k} $$
for any c such that $ 1 \leq c \leq k. $
Iterating k times, we have that
$$ g(k) = 2^k g(0) +\left ( 2^{k} -1 \right ) 2^{2^k}. $$
Back substituting for $ g(k) $ and $ k $, we get
$$ f(n) = f(2) \log_{2} n +\left ( \log_{2} n -1 \right ) n. $$
Rearranging,
$$ f(n) = (f(2) +n ) \log_{2} n -n, n = 2^{2^k}. $$

 

[alyafey22]

While all the other conditions of Case 3 of the Master Theorem hold, I don’t believe that the regularity condition,
$$ 2 \times 2^{k/2} \leq d \times 2^k, \ d < 1, \ k > N, $$
holds.
This holds for $ k \geq 2 \left (1-\log_{2} d \right ) $, but I don’t know…I’d like to have a numerical value for d that doesn’t depend on k. Maybe I’m wrong.

You need to find only one value for $0<d<1$ such that the regularity condition holds. Here we can choose $d = 1/2$

$$ 2^{k/2} \leq 2^{k-2}, \ k > 4 $$

$$ g(k) = 4 g(k-2) + 3 \times 2^{2^k} = 8 g(k-3) + 7 \times 2^{2^k} = … $$

I don't see how you obtained the coefficients of $2^{2^k}$ ?

 

[jacobi1]

You need to find only one value for $0<d<1$ such that the regularity condition holds. Here we can choose $d = 1/2$

$$ 2^{k/2} \leq 2^{k-2}, \ k > 4 $$

Oh, I see.

I don't see how you obtained the coefficients of $2^{2^k}$ ?

Since
$$ g(k) = 2 g(k-1) +2^{2^k}, $$
$$ g(k-1) = 2 g(k-2) + 2^{2^k}. $$
Substituting into the previous relation, we have that
$$ g(k) = 2 \left ( 2 g(k-2) +2^{2^k} \right ) +2^{2^k} = 4 g(k-2) + 2 \times 2^{2^k} + 2^{2^k} = 4 g(k-2) +3 \times 2^{2^k}. $$
Iterating c times, the coefficients of $ g(k-c) $ are $ 2^c $, and the coefficients of $ 2^{2^k} $ are $ 2^{c} - 1 $.

 

[alyafey22]

Oh, I see.Since
$$ g(k) = 2 g(k-1) +2^{2^k}, $$
$$ g(k-1) = 2 g(k-2) + \color{red}2^{2^k} $$

Ah, I think you missed to rewrite $2^{2^{k-1}}$

 

[jacobi1]

(Swearing)(Swearing)(Swearing)
I can't believe I made such a stupid mistake. Forgetting to substitute $k-1$ for $k$...

Anyway, if you iterate CORRECTLY k times, you get
$$ g(k) = 2^k g(0) + \sum_{j=0}^{k} 2^j 2^{2^{k-j}}.$$
Then,
$$ f(n) = f(2) \log_{2} n + \sum_{j=0}^{\log_{2} \log_{2} n } 2^j n^{2^{-j}}, $$
which I can't find an exact expression for (yet).