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

  • Thread starter Thread starter alyafey22
  • Start date Start date
AI Thread Summary
The discussion revolves around solving the recurrence formula f(n) = 2f(sqrt(n)) + n. While a bound for the function has been established, participants express skepticism about finding an exact solution. They explore various substitutions and transformations, such as letting n = 2^k and using the Master theorem, which suggests that f(n) grows at a rate of Θ(n). However, they encounter challenges with the regularity condition of the Master theorem and the complexity of deriving a simple expression for the sum involved in the recurrence. Overall, the consensus is that while bounds can be determined, an exact solution remains elusive.
alyafey22
Gold Member
MHB
Messages
1,556
Reaction score
2
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 ?
 
Physics news on Phys.org
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 :(
 
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)$$
 
Very sleek! I wonder if an exact solution exists now.. :confused:
 
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}. $$
 
Last edited:
jacobi said:
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}$ ?
 
ZaidAlyafey said:
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.

ZaidAlyafey said:
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 $.
 
jacobi said:
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}}$
 
(Swearing)(Swearing)(Swearing)
I can't believe I made such a stupid mistake. Forgetting to substitute $k-1$ for $k$...:mad:

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).
 
Last edited:

Similar threads

Replies
2
Views
1K
Replies
22
Views
5K
Replies
19
Views
3K
Replies
1
Views
2K
Replies
4
Views
1K
Replies
1
Views
2K
Back
Top