Log In Start studying!

Select your language

Suggested languages for you:

Americas

English (US)

Europe

Q40E

Expert-verified

Discrete Mathematics and its Applications

Found in: Page 217

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

Show that for all real numbers aand b with a>1 and b>1, if f(x) is O (log _bx), then f(x) is O (log _ax).

Hence we conclude f(x) is O (log _b x), then f(x) is O (log _a x)

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1

Given, f(x) is O (log _b x)

By the definition of Big-O notation, there exist a positive real number M ∋,

│f(x)│≤M│g(x)│, whenever x>k

Step 2

Consider,

│f(x)│≤M │log _b x │

=M $|\frac{\log_{a} x}{\log_{b} x}|$

= $= \frac{M}{\log_{b} x} |\log a x|$

Step 3

Let M₁= $\frac{M}{\log_{b} x}$ , then

│f(x)│≤M₁ │log _a x │ whenever x>k

Therefore by the definition of Big-O notation, f(x) is O (log _a x) with constant M and k.

Final answer

Hence we conclude f(x) is O (log _b x), then f(x) is O (log _a x)

Most popular questions for Math Textbooks

Show that the deferred acceptance algorithm terminates.

a) Describe an algorithm for finding the first and second largest elements in a list of integers.

b) Estimate the number of comparisons used.

a.) State the definition of the fact that f(n) is $O (g (n))$ , where $f (n)$ and $g (n)$ are functions from the set of positive integers to the set of real numbers.

b.) Use the definition of the fact that f(n) is $O (g (n))$ directly to prove or disprove that $n^{2} + 18 n + 107$ is $O (n^{3})$ .

c.) Use the definition of the fact that f(n) is $O (g (n))$ directly to prove or disprove that $n^{3}$ is $O (n^{2} + 18 n + 107)$ .

Define the statement $f (x, y) is Ω (g (x, y))$

Let $f_{1} (x)$ and data-custom-editor="chemistry" $f_{2} (x)$ be functions from the set of real numbers to the set of positive real numbers. Show that if $f_{1} (x)$ and data-custom-editor="chemistry" $f_{2} (x)$ are both $Θ (g (x))$ , where g(x) is a function from the set of real numbers to the set of positive real numbers, then $f_{1} (x)$ + $f_{2} (x)$ is $Θ (g (x))$ . Is this still true if $f_{1} (x)$ and $f_{2} (x)$ can take negative values?

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