I’m new to asymptotic notation and I’m struggling with some concepts. Can someone help me understand how to determine which side of the equation to divide when finding the constant c? For example, in proving 2n² = O(n³), do we divide 2n² or n³?
Also, I’m confused about the role of n₀ in the formula f(n) ≤ c·g(n) for n ≥ n₀. Why is it necessary and how do we use it?
Here’s a simple example I’m working with:
def example_function(n):
return 2 * n ** 2
def comparison_function(n):
return n ** 3
How would I go about proving that example_function is O(comparison_function)?
Any explanations or resources would be really helpful. Thanks!
I’ve been there, struggling with asymptotic notation too. Here’s what helped me:
For your example, you’re on the right track. To prove 2n² = O(n³), divide the left side by the right: 2n²/n³ = 2/n. This approaches 0 as n grows, showing that 2n² grows slower than n³.
Regarding n₀, it’s essential because some functions only settle into a predictable pattern after a certain point. Think of it as the starting line for when the Big O relationship consistently holds.
For your functions, try to establish 2n² ≤ c·n³ for n ≥ 1. Selecting c = 2 works, as the inequality holds for all n ≥ 1. A practical tip is to plot these functions to visualize their growth rates more clearly.
hi, for big o, divide the function by the comparision. so for 2n² = o(n³), u get 2/n. n₀ is the point after which the rule holds. for ur funcs, find a c so that 2n² ≤ c·n³ for n beyond a threshold. hope that helps!