Oct 10, 2018

[HDGEM] Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 2

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.

log(x^c)  = c * log(x)  
log2(f(n)^c) == c * log2(f(n))  
f(n)∗log2(f(n)^c) = c * f(n) * log2(f(n))                       = O(g(n)∗log2(g(n)))

Posted By Blogger to HDGEM at 3/06/2017 09:11:00 PM