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.
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.
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?