As this is it is not a recurrence relation as it stands.Originally Posted by hotmail590
It should look something like:
then as we would have:
RonL
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!
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
Would m be just a constant and this f(n) will be an O(n^(1/2))
therefore
is O(n^(1/2)). Is this correct? Thanks again for the help!!!