Results 1 to 4 of 4

Math Help - Recurrence Problem

  1. #1
    Newbie
    Joined
    Feb 2006
    Posts
    18

    Recurrence Problem

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote 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:

    <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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2006
    Posts
    18
    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!!!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2011, 06:45 AM
  2. Recurrence problem
    Posted in the Calculators Forum
    Replies: 2
    Last Post: November 24th 2009, 01:53 AM
  3. recurrence problem...
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: August 20th 2009, 05:43 PM
  4. Please Help! Recurrence Problem!
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 25th 2009, 01:44 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum