# Recurrence Problem

Printable View

• March 11th 2006, 10:11 PM
hotmail590
Recurrence Problem

Suppose that the function f satisfies the recurrence relation

2 * f ( sqrt(n) ) + log(n)

whenever n is a perfect square greater than 1 and f(2) = 1

For this problem I am asked to find f(16).

If I pluged in n = 16 into the function above I will get

2 * 4 + log(16) which equals to aprox. 9.204

9.204 is not a perfect square so does that mean when n=16 there is no answer?

I believe that we are supposed to plug the given n into the function and find its value, then if it is a perfect square, we plug that into the function again until that value is not a perfect square. Would this be correct?

Thank you very much for your help!
• March 12th 2006, 03:31 AM
CaptainBlack
Quote:

Originally Posted by hotmail590

Suppose that the function f satisfies the recurrence relation

2 * f ( sqrt(n) ) + log(n)

whenever n is a perfect square greater than 1 and f(2) = 1

As this is it is not a recurrence relation as it stands.

It should look something like:

$<br /> f(n)=2 f(\sqrt{n})+\log(n)<br />$

then as $f(2)=1$ we would have:

$<br /> f(16)=2f(4) +\log(16)=2 (2f(2)+\log(4))+\log(16)<br />$
$<br /> =2(2+\log(4))+\log(16)=4+2\log(4)+\log(16)<br />$

RonL
• March 12th 2006, 11:20 AM
hotmail590
Thanks again CaptianBlack for the help!

If I were to find a big O estimate for f(n) it would look like it is an O(log(n)) however I am not sure.

Also there was a hint given in finding the big O estimate (Hint: Make the subsitution m = log n)

What does that mean? If I replaced log(n) with m then f(n) would look something like the following

$<br /> f(n)=2 f(\sqrt{n})+ m <br />$

Would m be just a constant and this f(n) will be an O(n^(1/2))
therefore

$<br /> f(n)=2 f(\sqrt{n})+\log(n)<br />$

is O(n^(1/2)). Is this correct? Thanks again for the help!!!
• March 15th 2006, 05:10 AM
CaptainBlack
Quote:

Originally Posted by hotmail590
Thanks again CaptianBlack for the help!

If I were to find a big O estimate for f(n) it would look like it is an O(log(n)) however I am not sure.

Also there was a hint given in finding the big O estimate (Hint: Make the subsitution m = log n)

What does that mean? If I replaced log(n) with m then f(n) would look something like the following

$<br /> f(n)=2 f(\sqrt{n})+ m <br />$

Would m be just a constant and this f(n) will be an O(n^(1/2))
therefore

$<br /> f(n)=2 f(\sqrt{n})+\log(n)<br />$

is O(n^(1/2)). Is this correct? Thanks again for the help!!!

Is $n$ supposed to be equal to $2^{2^m}$ for some $m \in \mathbb{N_+}$ here?

RonL
All times are GMT -8. The time now is 11:33 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 11, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9479964375495911, "perplexity_flag": "middle"}