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)) $ ?