 Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q40E

Expert-verified Found in: Page 217 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Show that for all real numbers aand b with a>1 and b>1, if f(x) is O (log b x), then f(x) is O (log a x).

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 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$\left|\frac{{\mathrm{log}}_{a}x}{{\mathrm{log}}_{b}x}\right|$

= $=\frac{M}{{\mathrm{log}}_{b}x}\left|\mathrm{log}ax\right|$

## Step 3

Let M1=$\frac{M}{{\mathrm{log}}_{b}x}$ , then

│f(x)│≤M1 │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.

Hence we conclude f(x) is O (log b x), then f(x) is O (log a x) ### Want to see more solutions like these? 