Recurrence Problem

**hotmail590** · March 11th 2006, 10:11 PM

Can someone please help me with this 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!

**CaptainBlack** · March 12th 2006, 03:31 AM

Originally Posted by hotmail590

Can someone please help me with this 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

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

It should look something like:

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

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

$ f(16)=2f(4) +\log(16)=2 (2f(2)+\log(4))+\log(16) $

$ =2(2+\log(4))+\log(16)=4+2\log(4)+\log(16) $

RonL

**hotmail590** · March 12th 2006, 11:20 AM

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

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

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

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

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

**CaptainBlack** · March 15th 2006, 05:10 AM

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

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

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

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

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

Thread: Recurrence Problem

LinkBack

Thread Tools

Display

Recurrence Problem

Similar Math Help Forum Discussions

Recurrence relation problem

Recurrence problem

recurrence problem...

Please Help! Recurrence Problem!

Recurrence relation problem

Search Tags