algorithm - What is wrong with this reasoning to determine the upper bound? -
i given question in algorithm class
is 2^{2n} upper bounded o(3^n)? now clear 2^2n 4^n, , 4^n can't upper bounded 3^n.
however if take log on both sides
on lhs 2n on rhs kn (where k constant) 2n can upper bounded kn, contradicting of more obvious claim above. doing wrong in reasoning?
essentially, reasoning boils down statement:
if log f(n) ≤ c log g(n) constant c, f(n) = o(g(n)).
this statement isn't in general true statement, though. 1 way see find counterexamples:
if f(n) = n4 , g(n) = n, log f(n) = 4 log n , log g(n) = log n. it's true there's multiple of log n that's bigger 4 log n, n4 ≠ o(n).
if f(n) = 4n , g(n) = 2n, log f(n) = 2n , log g(n) = n. there's multiple of n makes bigger 2n, 4n ≠ o(2n).
to @ why doesn't work, notice c log g(n) = log g(n)c, multiplying log constant equivalent raising original function large power. can reason big-o of function multiplying constant, can't reason raising power, why reasoning breaks down.
Comments
Post a Comment