0
$\begingroup$

I always been very weak in Maths, because unfortunately I didn't really use maths since highschool.

In my algorithms & data structures class we are using the famous Big-O notation. I understand most of the basic concepts, more or less, so correct me if I'm wrong.

To determine the Big-O of an algorithm, block by block in the code, you build a formula that corresponds to the time complexity of your algorithm.

From $ O(1) $ for a simple assignment, to a $ O(n^2) $ for a nested loop. Then, from the expression you have, you get rid of the non-dominant terms and constants to finally have your "worst case scenario", which is the upper bound, which will be written as Big-O something.

But in my class the teacher plays a lot with some $ f(n) $ and $ g(n) $ functions, often asks us to do proofs :

$ f(n) = O(g(n)) $ if there exist a constant $ C > 0 $ and $ k \geq 1 $ such that $ f(n) \leq C(g(n)) $ for every $ n \geq k $

What isn't clear in my mind is :

What exactly is this $ f(n) $ function ? I know it is often referred as the "running time" of our algorithm. But if $ f(n) $ is the running time and has a Big-O of $ g(n) $, where does this $ f $ function come from ? How do we come with it ? Is it the formula we built analyzing the code block by block, and then $ g(n) $ the function keeping the dominant term ? In the teacher examples, $ f $ is often associated to a $ g $ of a very different form...

Also, what is the purpose of the constant $ C $ used for $ C(g(n)) $ ?

$\endgroup$
0
$\begingroup$

$O$-notation gives us a general way of comparing the growth rate of functions over the natural numbers. The functions $f$ and $g$ can be any functions; $O$-notation arose in number theory and is originally due to the German mathematician Landau. In the analysis of algorithms the functions that we are interested are usually functions that describe the time complexity of an algorithm (or a program). How this time complexity was arrived at, is of no importance to the definition.

By analogy: We can compare the mass of physical objects, but the definition of this does not require us to settle for some specific way of determining the mass of a physical object.

The constant $C$ that appears in the definition is introduced in order to ensure that the definition describes that $f$ can never "outgrow" $g$. The ratio $\frac{f(n)}{g(n)} \leq C$ (that is, at most a constant) as soon as $n$ gets large enough. In particular, this will ensure that functions that only differ by some constant factor have the same growth rate. In the analysis of algorithms this tells us that constant speed-up (or slowdown) does not really matter.

$\endgroup$
  • $\begingroup$ Thank you for those explanations. The way I was seeing $ C $ is that as $ g $ only keeps the dominant terms of $ f $ and get rids of everything else, we multiply $ g $ by a constant to compensate and be sure it will be above ? I may be wrong please tell me! $\endgroup$ – Scaraux Sep 3 '18 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.