Big O Notation

Big O:

Big O is denoted by O( ), and this refers to the worst-case scenario for our code’s runtime. Say, if we somehow happen to know the O( ) of our code, we can ensure that the code’s runtime will not be any longer than O( ) if the input is large.

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:

To determine the time complexity of an algorithm, we can follow two simple steps, and they are as follows:

--

--

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