The big O specifies 2 positive constants c and n_0 but there can be multiple c and n_0 values that are solutions. How can we decide which one is the best. What does having multiples solutions signify ?
In: 5
It characterises the growth rate of a function; completely different functions can have very similar growth rate (especially toward the limit).
What domain are you learning this in? As in some disciplines/uses the values of x could be restricted to positive integers, rather than positive real numbers or complex numbers with a positive real part.
Constants can be ignored especially for those f(x) which are multiplicative eg f(x) = 5x^3 + 17x^2 + 3x. As x gets large, the x^3 term dominates more and more and the constants, 5, 17, 3 more and more irrelevant. So you could set that 17 to 1 and it will not make a big difference to the big-O evaluation of the function: it’s polynomial.
You don’t decide which one is best, none of them are best, and you don’t pay attention to them.
The definitions say “there exist a c, n_0, …” not because you’re supposed to find out what those c, n_0 are.
Even if you did bother to find them, the only reasonable thing to do with them would be to throw them in the garbage and forget about them immediately.
Think of it this way.
We can define a house to be “certified” if there exists an electrician who has examined it and said it’s safe.
You could say, but there could be multiple electricians!
You could have any number of electricians look at the house and say it’s safe!
How do we decide which electrician is the best?
What implications are there at having so many electricians certify the house??
And the answer is, none of it matters.
As soon as the house is certified, the house is certified.
Nobody cares who the electrician was.
If your goal is only to get a certification saying that the house is safe, there’s no point trying to define which electrician did the best job of saying “it’s safe”.
With Big-O, your only goal is to show that the function is bounded by another function.
The n_0 and c values are the electrician who says “yes, it’s bounded!”.
Okay, good, job done.
We don’t care about the specific values used.
Big o notation is useful for situations like this: I have tested my code on a small input dataset of 1000 entries, and it took ten seconds to run. I’d now like to analyze a million entries. How long will that take? A few hours? A few months? Years? Centuries?
All of these are possible depending on the complexity of the algorithm. Since it’s the same algorithm in either case the multiplicative constant is identical and since the numbers are huge the additive constant is irrelevant: all that matters is the power of N.
Big O notation simply communicates the relationship between inputs and operations. Does the code have a linear relationship, how about an exponential one?
That is all you care about when looking at the efficiency of an algorithm.
Latest Answers