Consider f(n) = 3n^2+2n-1, mathematically show that f(n) is O(n²), (n²), and O(n²).
Consider f(n) = 3n^2+2n-1, mathematically show that f(n) is O(n²), (n²), and O(n²).
a) answer:
f(n) = O(g(n)) means there are positive constants c and n0, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
3n^2 + 2n - 1 = O(n^2)
=> 3n^2 + 2n - 1 <= c(n^2)
Let's assume c = 4
=> 3n^2 + 2n - 1 <= c(n^2)
=> 3n^2 + 2n - 1 <= 4(n^2)
=> 2n - 1 <= n^2
it's true for all n >= 1
so, 3n^2 + 2n - 1 = O(n^2) given c = 4 and n0 = 1, using the definition of Big-O
b) answer:
f(n) = Ω(g(n)) means there are positive constants c and n0, such that f(n) >= cg(n) for all n ≥ n0
3n^2 + 2n - 1 = Ω(n^2)
=> 3n^2 + 2n - 1 >= c(n^2)
Let's assume c = 1
=> 3n^2 + 2n - 1 >= c(n^2)
=> 3n^2 + 2n - 1 >= 1(n^2)
=> 2n^2 + 2n - 1 >= 0
This above equation is true, for all n >= 1
so, 3n^2 + 2n - 1 = Ω(n^2) given c = 1 and n0 = 1, using the definition of Ω
Step by step
Solved in 2 steps
