+1 vote
27 views

In this question if we solve using logarithm we get time complexity of $g(n)>f(n)=h(n)$

But is taking $logarithm$ to find out the complexity always a safe way? I believe $NOT$. To support my claim I provide u with this link→ https://cs.stackexchange.com/questions/117577/which-grows-faster-factorial-or-double-exponentiation (Go through the comments of the selected ans)

Similarly, here we can also see that $n^{100}$ has larger complexity than $n!$ for values like 2,3,4….even 100. I do not know where the graph of f(n) and g(n) intersects and g(n) upper bounds f(n)

What is the best approach to solve then? as if I plug in large values computable by our $GATE$ calculator I get $n^{100}$ runtime higher than g(n) and on the other hand comparison with the help of log is an horrible idea in some case as $logf(n)=O(log$ $g(n))$ doesn't always means $f(n)=O(g(n)$ for example let $f(n)=n^2$ and $g(n)=n$ then $f(n)\neq O(g(n))$ but $logf(n)=O(log$ $g(n))$

So what is the approach to solve this problems to be $100\%$ sure about the ans?

edited | 27 views
0
+1
In general remember the increasing order of complexities:

constant divided by polynomial < constant < $logn$ < $(logn)^k$ < $n$ < $nlogn$ < $n(logn)^k$ < $n^k$ < $n^k(logn)^l$ < $n^{k+l}$ < $d^n$

Use this as a first level of analysis and eliminate some of the options.

When not to use logarithm method : if, after applying logarithm, you get some constant or a constant multiple/factor.

example: $n^2$ and $n^{100}$. If you apply logarithms, both are same complexity - though you know they are not.

If using 'sufficiently large numbers' - be judicious in choosing the large numbers. And don't stop with one trial. Perform the test with 2 sufficiently large numbers, and then take the ratio of the two trials for each function - to identify which grows the largest. I like to choose powers of 2, like $2^{1024}$,  $2^{256}$ - since they'll also work if you have $loglogn$.

Unfortunately there is no one-size-fits-all approach. You need to use everything you know about function growth and intuition to reach the solution.
0
So in this case as u can see we have $n^{100}$ and $n!$ how will you determine which is asymptotically larger?
+1
$n!$ is exponential in $n$ ($n! \rightarrow n^n$ by Stirling's Approximation). Exponential is clearly larger than polynomial.
0
OK

Thanks again.. :)