0

How can I formally classify a function that increases to infinity?

Intuitively I know (I don't why I know it, maybe from school) that functions like:

$$f(n) = n^2 + n + 123 + log_2n$$ $$f(n) = n^2 + n$$ $$f(n) = 12 * n^2$$

Have quadratic class

Functions like:

$$f(n) = log_2n + 2$$ $$f(n) = 5 + log_5n + 2$$

Have logarithmic class

I did this classification because it is obvious for me that $n^2$ has higher growth rate than $n$ and $n$ has higher growth rate than $log_2n$

But do we have any common and formal way to classify a function?

Or more commonly speaking, what does exactly word class means when we talk about functions?

UPDATE: Someone suggested me that I should look at Big O notation. I don't see how it can solve my problem.

Let's say we have a function like: $$f(n) = 2^{(n + log_2n +12)} + 3^{(5n + log_2n)}$$

How Big O can help me to determine at what set (class) of functions $f(n)$ belongs to?

Moreover, we can use Big O notation only after function is been classified, not before. So I need some math framework to classify function and only then I can use Big O notation.

No Name QA
  • 163
  • If you're talking about functions that increase to infinity, you can classify them using Big-O notation: https://en.wikipedia.org/wiki/Big_O_notation – Franklin Pezzuti Dyer Oct 24 '18 at 20:49
  • @RushabhMehta Please see my update – No Name QA Oct 24 '18 at 20:59
  • @Frpzzd please see my update – No Name QA Oct 24 '18 at 21:02
  • @Frpzzd also my question contains question what word class means. And I don't think that word class means Big O Notation. – No Name QA Oct 24 '18 at 21:03
  • @RushabhMehta This is not a duplicate of that question, by any means. – Franklin Pezzuti Dyer Oct 24 '18 at 21:06
  • I think what you really want is Theta perhaps with some o(1) floating around instead of just the big O, i.e. a tight bound rather than just an upper bound (you don't want to call $f(n)=\log n$ a quadratic, but $f\in O(n^2)$). There is also the problem of how finely you want to partition (e.g., do you want to have $c^n$ for every real $c>1$ distinct or just an "exponential" class). – user10354138 Oct 25 '18 at 01:33

0 Answers0