CODEWITHSUNDEEP
asymptotic-complexity
Charu
Charu

Reputation: 2749

If f(n)=O(g(n)), then shouldn't f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) depend on the value of C?

If f(n)=O(g(n)), then shouldn't f(n)∗log2(f(n)^c)=O(g(n)∗log2(g(n))) depend on the value of C?

Here C is a positive constant. According to me if C is large then the statement would become false and if c is small it'd be true. Hence the outcome is dependent on c.

I am taking a class on algorithms and this is one of the questions I was asked. According to me this should be dependent on constant c but the answer was wrong.

Upvotes: 13

Views: 12954

Answers (4)

101
101

Reputation: 1

Solving for the Left hand side,

= f(n) * log2(f(n)^c)
= f(n) * c * log2(f(n)

Now since f(n) = O(g(n)) are precisely equal. We can write,

= c * g(n) * log2(g(n))

After taking the Big-Oh notation of the above statements,

= c * O(g(n)*log2(g(n))
= O(g(n)*log2(g(n))

Now try graphing xlog2(x) * constant on a graphing calculator or Desmos, you will see for positive y = x or simply x values, graph doesn't change as you try to increase constant c's value. You can also prove this by the definition of "Big-Oh".

Upvotes: 0

vCillusion
vCillusion

Reputation: 1799

Given,

  1. f and g are non-decreasing real-valued functions on positive integers and at least 2 for n >= 1
  2. f(n) = O(g(n)), g(n) <= c1 f(n) and log (g(n)) <= log (c2 f(n)) Using 1 and 2, we know that g(n) is bounded by c f(n), and f and g are non-decreasing functions, as deduced below.

Using 1 and 2, start from g(n) * log2 (g(n))

g(n) * log2 (g(n)) <= c1 f(n) * log2 (c2*f(n))
g(n) * log2 (g(n)) <= c1 f(n) * (log2 c2 + log2 f(n))
g(n) * log2 (g(n)) <= c1 f(n) * log2 c2 + c1 f(n) * log2 f(n)
g(n) * log2 (g(n)) <= c1 * log2 c2 * f(n) + c1 f(n) * log2 f(n) <= c1 * log2 c2 * f(n) * log2 f(n)
g(n) * log2 (g(n)) <= c * f(n) * log2 f(n)
g(n) * log2 (g(n)) <= O(f(n) * log2 f(n))
QED

Upvotes: 0

Ryan E Washburn
Ryan E Washburn

Reputation: 31

@Undefitied, By the definition of Big-Oh notation f(n) = O(g(n)) if and only if there exists a constant "c" and an N such that f(n) <= c*f(n) for all n > N. When we assert f(n) is "equal" to O(g(n)), we are not saying they are necessarily "equal" in algebraic terms. We are saying f(n) is bounded above by g(n). If f and g are nondecreasing and always bigger than one, and c is a positive constant, the proof given above by Mitch Wheat is true.

Upvotes: 3

Mitch Wheat
Mitch Wheat

Reputation: 300559

log(x^c)  = c * log(x)

So,

log2(f(n)^c) == c * log2(f(n))

Therefore,

f(n)∗log2(f(n)^c) = c * f(n) * log2(f(n))

                   = O(g(n)∗log2(g(n)))

Upvotes: 25

Related Questions