Unity+ Posted March 11, 2015 Share Posted March 11, 2015 The problem is asking the following: Determine if the following function is O(x^2). f(x) = 17x+11 I attempted the problem by doing the following: Since the highest degree is 1, the following function is valid. Now, let's set c = 17. 17x + 11 <= 17x^2 x + (11/17) <= x^2 Since x = 2 is the lowest natural number that makes the statement true, c = 17 and k = 2. Is this done right? Link to comment Share on other sites More sharing options...
John Posted March 11, 2015 Share Posted March 11, 2015 (edited) Depending on what exactly your instructor expects, this may be a valid answer.However, a couple of things:1. Formally, using the definition, the statement is true, but is O(x2) the tightest bound? 2. Keep in mind that c and k aren't restricted to being natural numbers. I mention this only because it seems like you're looking for the smallest values. Edited March 11, 2015 by John 1 Link to comment Share on other sites More sharing options...
studiot Posted March 11, 2015 Share Posted March 11, 2015 Why did you choose C = 17? Proving the statement [math]17x + 11 = O({x^2})[/math] means find a C and k such that [math]\left| {17x + 11} \right| \le C{x^2}:\left| x \right| \ge k[/math] Echoing what John said, I am not sure why you included discrete in the title? For discrete structures we usually use n as the variable. x usually refers to real numbers in which case the inequality would be true for all x except within an interval determined by C an k. If x was complex then it would all x outside some disk of radius k, as John says. 1 Link to comment Share on other sites More sharing options...
Unity+ Posted March 13, 2015 Author Share Posted March 13, 2015 Depending on what exactly your instructor expects, this may be a valid answer. However, a couple of things: 1. Formally, using the definition, the statement is true, but is O(x2) the tightest bound? 2. Keep in mind that c and k aren't restricted to being natural numbers. I mention this only because it seems like you're looking for the smallest values. The teacher stated that any number works, since k and c are simply "witnesses" to whether O(g(x) represents the function. The problem was just asking for O(x^2). Thanks for the help, btw. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now