Question

You are given functions f and g such that f(n)=O(g(n)). Is f(n)∗log2(f(n)c)=O(g(n)∗log2(g(n))) ? (Here c is some constant >0. You can assume that f and g are always bigger than 1.

a) true
b)false
c)depends on c
d) depends on f and g

Answer 1

I think could go this way:
f(n)=O(g(n)) means |f(n)|<= M |g(n)| or |f(n)|/|g(n)| <= M
so you have to prove, given that f(n)=O(g(n)), that |f(n)∗log2(f(n)c)|/|g(n)∗log2(g(n))| <= N
|f(n)∗log2(f(n)c)|/|g(n)∗log2(g(n))| <= M|log2f(n)c)|/|log2(g(n))| =
=M log2|(f(n)c -g(n))| <= M log2 (|M|g(n)|c - g(n)|).
So i think it depends on c.

Answer 2

@saranya

Answer 3

i am going to guess no
\[f=O(g)\iff \lim_{n\to \infty}\frac{f}{g}=M\] for some M if i remember correctly
so you want \(\lim_{n\to \infty}\frac{f(n)\log(cf(n))}{g(n)\log(g(n))}\) to be finite
i guess it comes down to computing \(\lim_{n\to\infty}\frac{\log(cf(n))}{\log(g(n))}\)

Answer 4

But acc. to Big oh Definiton it is true ryt ?

Answer 5

\[\lim_{n\to \infty}\frac{\log(c)+\log(f(n))}{\log(g(n))}\]
so i guess as long as \(\lim_{n\to \infty} g(n)\neq 1\) you are ok
hmmm

Answer 6

it is early so i would make no bets on this, but i am going to say it does not depend on c
of course you will want a proof, but maybe before you try one do it by example. i.e. check with some functions you know and see what happens

Answer 7

yea okay thanks :)

Answer 8

sorry i cannot provide an actual solution
good luck

Answer 9

no probs :)

Answer 10

Can anyone help out this question....?
Arrange the following functions in increasing order of growth rate. ie. if g(n) follows f(n) in your list, then f(n) is necessarily O(g(n)).

a)2^2n
b)2^n^2
c)n^2log(n)
d)n
e)n^2n

Answer 11

@ satellite can yu reply m for this ??

Answer 12

f cannot be same as g since from the defn of f(n) = O(g), f != g

Answer 13

but one can as well argue that since both f and g have no relationship but all positive, it is pointless to compare both in that sense....u should revise definitions of big O and their relation in order to argue properly