Big O Notation

Big O:

Steps to find O( ):

  1. Determine T(n) of your code
  2. Find a suitable X(n) that behaves similar to T(n)
  3. Tune C to a higher (if X(n) resides below T(n)) or a lower value (if X(n) resides above T(n)) to move X(n) just above T(n). X(n) should not be far above T(n)
  4. If X(n) is upper-bounding T(n) asymptotically (it can upper-bound T(n) at smaller n values as well), then we can say O(X(n)) is our desired upper-bound. It implies if n increases rapidly, then the runtime will follow X(n)’s behavior.
Bounding of T(n) by X(n)

Shortcut:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store