1
$\begingroup$

I have the following functions:

enter image description here

  1. What is the correct order of these functions in increasing complexity?

  2. I could always start entering values in these functions and check the corresponding output to notice the rate of increase. But is there a better, faster way of ranking these functions in order of increasing complexity? For example are there rules of thumb I could use to quickly sort these in order of increasing complexity? (Like I know generally exponential functions are more complex than log functions)

$\endgroup$
  • 2
    $\begingroup$ Have you heard of asymptotic notation, and in particular of big-Oh notation? I have a feeling that you may not. $\endgroup$ – Hans Hüttel Oct 16 '16 at 22:41
  • $\begingroup$ Approach 2 is badly flawed. Finite samples never prove asymptotics! It can be useful to form hypotheses, though. $\endgroup$ – Raphael Oct 18 '16 at 9:39
  • $\begingroup$ Be careful with the use of the term "complex" here. Are you comparing the asymptotic growth of the functions lists, or the "complexity" of computing them? $\endgroup$ – Raphael Oct 18 '16 at 9:39
  • $\begingroup$ Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Oct 18 '16 at 9:41
1
$\begingroup$

I solved it after understanding asymptotic notation and the complexity of some common functions. Here's the order from least expensive to most expensive:

log log n, log n ~ ln n, (log n)^2, sqrt(n), n, n log n, n^(1+x), n^2, n^3, n-n^3+7n^5, 2^(n-1) ~ 2^n, e^n, n!

$\endgroup$
  • $\begingroup$ How/why did you rank $\log n$ vs $\ln n$? Or $2^{n-1}$ vs $2^n$? $\endgroup$ – Raphael Oct 18 '16 at 9:40
  • $\begingroup$ They are both equal. I edited my post to reflect that now. $\endgroup$ – learnerX Oct 18 '16 at 9:42
  • $\begingroup$ They are clearly not equal. $\endgroup$ – Raphael Oct 18 '16 at 10:02
  • $\begingroup$ I thought they were nearly equal in terms on asymptotic growth? Our teacher asked us to indicate when 2 functions were asymptotically equal. $\endgroup$ – learnerX Oct 18 '16 at 12:20
  • $\begingroup$ Asymptotically equal w.r.t $\Theta$ or $\sim$ or ... ? ("$=$" typically means exact equality so you don't want to use that symbol.) $\endgroup$ – Raphael Oct 18 '16 at 14:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.