• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Answers without the blur. Sign up and see all textbooks for free! Illustration


Discrete Mathematics and its Applications
Found in: Page 535
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.


Short Answer

Suppose that the function f satisfies the recurrence relation f(n)=2f(n)+logn whenever n is a perfect square greater than 1and f(2) = 1.

a) Find f(16).

b) Give a big -Oestimate forf(n). [Hint: Make the substitution m=logn].

(a) The required function f(16) = 12.

(b) The required function f(n)=O(lognloglogn).

See the step by step solution

Step by Step Solution

Step 1: Given information

The functionfsatisfies the recurrence relation f(n)=2f(n)+1, Where nis a perfect square greater than1andf(2) = 1.

Step 2: Explain the Master theorem

The master theorem is a formula for solving recurrence relations of the form: T(n)=aT(n/b)+f(n), where n= the size of the input a= number of sub-problems is in the recursion n/b=size of each subproblem. All subproblems are assumed to have the same size.

Step 3: Calculate the functionf(16)


To find f(16):




Step 4: Calculate the value off(n)by the Master theorem


Use the suggested substitution and let m=logn.


Now, it will may be f(n)=f2m.


Rewrite the function, for clarity, as g(m)=f2m.

And so,g(m) = 2g(m/2) + m .

Next, apply the Master theorem with a=2,b=2,c=1,d=1:


Hence, f(n)=O(lognloglogn)

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.