Big O notation mathematical formula

I recently started learning Data Structures and Algorithms. I cam across the mathematical definition of Big O notation. It was as follows,

f(n)=O(g(n)) iff f(n)<= C. g(n) for all n0

Now as the Big O says, it measures performance of algorithm by providing order of growth of function.
But here what is exactly f(n), g(n) and how and from where did the C and n0 came into the picture. I am really very much confused here. I want a very easy and clear explanation on this regardless of fancy english explanation, as I am not examining the IELTS interview.

I like this explanation:

Unfortunately, it is not solution to my question. I am looking someone to explain the formula mentioned. Please help with it.

The formula is the compact version of that entire article.

Let me resummarize the article for you.

Suppose we have a sorting algorithm. This sorting algorithm takes 4 seconds to sort a list of 10 numbers and 400 seconds to sort a list of 100 numbers.

This means that the total runtime as a function of the number of items in the list is given by

f(n) ≈ 0.4 n²

where f(n) is the approximate runtime and n is the size of the list.

We can say that

f(n) ≈ 0.04 n² ≤ C g(n)

where C = 0.04 and g(n) = n².

We can therefore say that f(n) ∈ O(n²).

Or, in other words, that formula is a compact way to say

If we instead have an O(n²) algorithm for sorting a list, then we should expect that the amount of time we take will increase quadratically as we increase the size of our list.

A list that has 10 times as many numbers will take approximately 100 times as long to sort! This means that if sorting 10 numbers takes us 4 seconds, then we would expect sorting a list of 100 numbers to take us approximately 400 seconds.

3 Likes

See, I’m really glad that you got my question and you are very close to solution that I am expecting. Almost you’re very close but just clarify me on some terms I’m confused on right now.
So, I got what you want to say. But tell me on first you defined

I want to confirm if it is 0.04. and after that you really got my point was the definition of C. Why and how C=0.04? what’s the reason it is?

C is a constant; it is only relevant in a rigorous mathematical proof of big O.

I got C = 0.04 because f(10) = 4 and f(100) = 400, so I see quadratic growth and need a C such that f(10) = C 10² = 4 and f(100) = C 100² = 400.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.