2

According to this book (section 3.1 Order of growth): An order of growth is a set of functions whose asymptotic growth behavior is considered equivalent. 

I'm trying to find more precise definition about order of growth. If I understand author's definition correctly he meant the following:

Order of growth of f(n) function is a set of all functions, such that the following statement is always true:

$$ \lim_{n\to \infty} \frac{f(n)}{C*g(n)} = 1 $$

where $C > 0$

Therefore, if $f(n) = 12 * n^2 + n + 14$ then order of growth can be any of the following functions:

$$g(n) = n^2$$ $$g(n) = 12*n^2$$ $$g(n) = 12*n^2 + 1$$ $$g(n) = 12*n^2 + log_2n$$ $$etc$$

So, basically I think it will be correct to say that the order of growth of f(n) function is just it leading term without a constant: $$f(n) = 12 * n^2 + n + log_2n$$ Order of growth of $f(n)$ $$g(n) = n^2$$

The question is: Is my reasoning are correct?

No Name QA
  • 163
  • 2
    There's not always an obvious leading term in a general function, which is why we need the limit definition. Consider a function defined by an integral, or an ODE – Yuriy S Oct 23 '18 at 17:29
  • @YuriyS Let's say that we have a function with obvious leading term. Does it mean that in this case my reasoning is correct? – No Name QA Oct 23 '18 at 17:31
  • 2
    Your reasoning is correct for polynomials. But most functions don't have a "leading term" in the sense you hope for. What about $e^x$? – Ethan Bolker Oct 23 '18 at 17:31
  • @EthanBolker So, if we talk only about polynomials leading terms will be order of growth. Got it. Could you, please, say what we should do in other cases? – No Name QA Oct 23 '18 at 17:33
  • 1
    If you can explain why an "obvious leading term" actually dominates the other terms then you can use it for the order of growth. But that requires argument. In your example, how do you know $n^2$ is "more leading" than $\lg_2(n)$? That requires knowing something.about the logarithm. In those :other cases" you have to look at all the terms. There's no magic trick. – Ethan Bolker Oct 23 '18 at 17:33
  • @EthanBolker That the prefect question! We could use L'Hospital rule to find out that $n^2$ has higher growth rate than $log_2n$ – No Name QA Oct 23 '18 at 17:36
  • 1
    Yes, L'Hopital will work there. (But I really dislike L'Hopital and many here share that dislike. Search "limit without L'Hopital" for examples and reasons and alternative stragies.) – Ethan Bolker Oct 23 '18 at 17:41
  • @EthanBolker Thank you. One more question, to make things clear: Does my definition of order of growth using limits is correct? – No Name QA Oct 23 '18 at 17:46
  • Almost, and usually. But $\sin(x)$ and the function $1$ have the same order of growth even though your definition using limits won't work. A web search for "order of growth" will find correct technical definitions in lots of places. – Ethan Bolker Oct 23 '18 at 17:50
  • @EthanBolker I have googled order of growth every day, about 3 weeks in a row. Everything I have found is about programming. I did not find any correct technical definition. The only "not so bad definition" I have found is a link in my original question. I will be very grateful if you will provide me a link with technical definition of order of growth – No Name QA Oct 23 '18 at 17:55
  • https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition . Two functions have t he same order of growth if each is big-O of the other. No more comments here. – Ethan Bolker Oct 23 '18 at 18:14
  • @EthanBolker it says nothing about what is order of growth. What you have wrote it like said: if two cars are marked as 4matic it means that both have 4 wheels drive. This definition does not give as any definition what 4 wheel drive is. – No Name QA Oct 23 '18 at 18:22
  • Although it is tempting to use code format for emphasis, it causes difficulty for screen readers used by visually impaired Readers. For this reason it's recommended that italic emphasis (Markdown asterisk delimiters) be used instead. – hardmath Oct 24 '18 at 13:09

0 Answers0