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

thanks myko was really stuck on this

Answer 3

not 100% sure , :). Just an idea

Answer 4

well sumthing is better than none

Answer 5

:)

Answer 6

for two (positive) functions f and g such that f(n)=O(g(n)). Is 2f(n)=O(2g(n)) ? (Multiple answers may be correct.)
Sometimes
Never
Yes if f(n)≤g(n) for all sufficiently large n
Always

Answer 7

if i am not wrong for it the answer should be Yes if f(n)≤g(n) for all sufficiently large n

Answer 8

2|f(n)|/2|g(n)| =|f(n)|/|g(n)|<= M
so always, i would say. By the way you can take out the ||, since functions always positive

Answer 9

Is 2f(n)=O(2g(n)) ? (

Answer 10

Always

Answer 11

actually it is 0(2powg(n))

Answer 12

if f(n)=O(g(n)), then 2f(n)=O(2g(n))

Answer 13

ai get that but the qquestion is 2f(n)=O(2powerg(n))

Answer 14

you mean?
\[2f(n) =O(2^{g(n)})\]