Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q10E

Expert-verified

Discrete Mathematics and its Applications

Found in: Page 535

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.

Register for Free I’ll do it later

Short Answer

Find $f (n)$ when $n = 2^{k}$ , where $f$ satisfies the recurrence relation $f (n) = f (n / 2) + 1$ with $f (1) = 1$ .

Thus, $n = 2^{k}$ is equivalent with $k = \log_{2} n$ .

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms: $f(n) = a f(n / b) + c$

Step 2: Apply Recurrence Relation

Given information are $n = 2^{k}, f (n) = f (n / 2) + 1 and f (1) = 1$

Repeatedly apply the recurrence relation:

$f (n) = f (2^{k}) f (n) = f (2^{k - 1}) + 1 f (n) = f (2^{k - 2}) + 2 f (n) = \dots f (n) = f (2^{2}) + (k - 2) f (n) = f (2^{1}) + (k - 1) f (n) = f (2^{0}) + k f (n) = f (1) + k f (n) = 1 + k f (n) = k + 1 f (n) = \log_{2} n + 1$

Therefore, $n = 2^{k}$ is equivalent with $k = \log_{2} n$ .

Most popular questions for Math Textbooks

Use Exercise 29 to show that if $a = b^{d}$ , then $f (n)$ is $O (n^{d} l o g n)$ .

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

a) Find\(f(16)\).

b) Give a big- \(O\) estimate for\(f(n)\). (Hint: Make the substitution\(m = \log n\)).

Suppose that each person in a group of \(n\) people votes for exactly two people from a slate of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than \(n/2\)votes.

a) Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received at least \(n/2\)votes and, if so, determine who these two candidates are.

b) Use the master theorem to give a big- \(O\) estimate for the number of comparisons needed by the algorithm you devised in part (a).

Find $f (n)$ when $n = 2^{k}$ , where $f$ satisfies the recurrence relation

$f (n) = 8 f (n / 2) + n^{2}$ with $f (1) = 1$ .

Solve the recurrence relation $T (n) = n T^{2} (n / 2)$ with the initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer. [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = l o g T (2^{k})$ to obtain a linear non-homogeneous recurrence relation.]

Want to see more solutions like these?

Sign up for free to discover our expert answers

Get Started - It’s free

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free