1

I am trying to wrap my head around big O notation and am quickly stuck just trying to understand the the mathematical jargon that is thrown around. It has been a long time since I touched that type of math and therefore need a refresher course.

Some of the terms that are looking foreign to me (but definitely not all), include: log, function, n!, √, etc.

Which mathematic skills are necessary to understand big-o notation on a basic level? Is that just basic algebra?

zeckdude
  • 127
  • 2
    I would say that you should have a familiarity with calculus in order to really get big O notation, since most of the statements will revolve around taking a limit. Other than that, familiarity with the various standard functions like $\log$, $\exp$, and powers of $x$ should be all you need. – Valborg Mar 26 '18 at 03:54
  • Do you have a particular big O statement you would like to discuss to help elucidate the situation? – Valborg Mar 26 '18 at 03:55
  • Calculus is sufficient, for the reasons Valborg mentioned. For the basics, precalculus is really necessary. You may find the following links helpful: http://www.dreamincode.net/forums/topic/280815-introduction-to-proofs-induction-and-big-o/ http://www.dreamincode.net/forums/topic/321402-introduction-to-computational-complexity/ – ml0105 Mar 26 '18 at 03:57
  • Thanks for the comment. I don't have a specific problem yet as I have barely scratched the surface and am already lost in all the jargon. Gaining the familiarity for the various standard functions, is that Algebra or Calculus? – zeckdude Mar 26 '18 at 03:57
  • @zeckdude I would say that it is both, especially if you are on uncertain ground with square roots. You won't see $\log$ and $n!$ until a calculus course though, probably. – Valborg Mar 26 '18 at 03:59
  • @Valborg Where I'm from (the US), that's taught 2 years before calculus. – Andrew Li Mar 26 '18 at 04:03
  • @AndrewLi Really? My students last semester had a tremendous amount of difficulty understanding logarithms and exponentials, and they were ostensibly supposed to be ready for the calculus 1 class they were taking, lol. Yay US math education! – Valborg Mar 26 '18 at 04:14
  • @Valborg I wouldn't say thoroughly (many that are introduced to it in the course Algebra II do not understand its derivation or even use because of rote memorization). Factorials aren't discussed though (unless you count some very small sprinkles of probability and binomial theorem here and there). – Andrew Li Mar 26 '18 at 04:19

1 Answers1

1

In big-O we don't care about multiplicative constants and only care about the term that is the largest as $n$ gets large. Taking $n$ as the variable, $a$ as some fixed number, and $b$ as some fixed number with $a \gt b \gt 1$ you should prove and be very comfortable with $$n^n \gt n! \gt a^n \gt b^n \gt n^a \gt n^b\gt n^{1/b} \gt n^{1/a} \gt (\ln n)^a$$ where the greater than signs mean eventually (as $n$ gets large) so much greater that it overwhelms any multiplicative constant.

Ross Millikan
  • 374,822