I’m trying to wrap my head around asymptotic notation and I’m stuck on a few points. The basic formula seems straightforward:
f(n) <= c.g(n) where n >= n₀
But I’m confused about how to find ‘c’ and what role n₀ plays.
For example, if we’re trying to prove that 2n² = O(n³), do we divide 2n² or n³ to find c? I’ve seen examples doing it both ways and I’m not sure which is correct.
Also, what’s the deal with n₀? I get that n should be greater than or equal to it, but why do we need it? Can’t we just find c and n to determine if one function is big O of another?
If anyone could break this down for me or point me to some good resources, I’d really appreciate it. I’ve looked at a few online lectures but I’m still feeling lost. Thanks for any help!
yo, i get ur confusion. asymptotic stuff can be tricky. for finding c, divide the function you’re proving by the big O function. so 2n²/n³ = 2/n. n₀ is like the starting point where the relationship kicks in. it’s important cuz some functions act weird at first. don’t stress too much about exact values tho. focus on how they grow compared to each other as n gets huge. hope that helps!
As someone who’s grappled with asymptotic notation, I totally get your confusion. It can be a real head-scratcher at first! Here’s what helped me understand it better:
The constant ‘c’ is like a scaling factor. You’re trying to find a value that makes g(n) grow at least as fast as f(n) for large n. In your example with 2n² = O(n³), you’d divide 2n² by n³ to get 2/n, which is always less than 2 for n > 1. So c = 2 works here.
As for n₀, it’s crucial because some functions only behave as expected after a certain point. It’s like saying, ‘This relationship holds true for all values of n after this threshold.’ Without it, you might have cases where the relationship doesn’t hold for small n.
In practice, you often don’t need to find exact values for c and n₀. The key is proving they exist. It’s more about understanding the growth rate relationship between functions as n approaches infinity.
I’ve found that thinking about asymptotic notation in real-world terms can be helpful. Consider ‘c’ as a buffer zone - it gives you some wiggle room when comparing functions. For 2n² = O(n³), you’re essentially asking if n³ will always outgrow 2n² given enough time (or a large enough n).
The n₀ concept is like a starting line in a race. Before this point, the functions might behave erratically, but after n₀, the true growth patterns emerge. It’s crucial for establishing when the Big O relationship kicks in.
In practice, you don’t always need to calculate exact values. The goal is to prove the relationship exists. Focus on understanding how functions grow relative to each other as n increases. This perspective has helped me grasp the concepts more intuitively.