- #1
vr0nvr0n
- 20
- 0
Let me start by saying that this is from a 30 question assessment on Big Oh, Big Theta, and Big Omega. I understood every other question, however, even after being given the correct answer, I do not understand why my answer was wrong for this one. If you could point me in the direction of any resource that helps explain why my answer was incorrect, I would GREATLY appreciate it (or, of course, any explanation here is appreciated, even more so!).
The question is this: Find the best Big-O function for the function |n + 2| − |n / 3|.
And here are the options (all logs are in base 2):
1. log(n)
2. n3
3. n
4. n2
5. n4
6. n * log(n)
I should state here that what I inferred from this question was that the "best Big-O function" was the one that was the most closely bounded to the original function, so n20 would be an incorrect, through technically accurate, answer.
Relevant equations are, of course, our given function: |n + 2| − |n / 3| (in the question, it is not referred to as f(n), but I will refer to it as this for ease of reference in the next equation)
And, the definition of Big Oh, which tells us that if for some constant c and some number k where all n>=k,
if |f(n)|<= c|g(n)| for all of n, then g is Big Oh of f.
By finding the least common denominator, we can write |n + 2| − |n / 3| as 2n/3 + 2 (since we are interested in what is going on as n becomes large, and when n = 0, the function is positive -- with an answer of 2 -- I expected combining these functions would be fine. This may be where the issue arose, however, if that's the case it is still unclear to me why this would be wrong).
Now, if we ignore constants, we can write this is 2n/3. Since, for all n>=k when k = 0 and when c = 1, it is the case that |2n/3|<= 1|n|, I determined that the best answer for this was n (also, since the equation moves in a linear way, this made sense by inspection before working this out).
This was incorrect and I was informed the correct answer was log(n) where the log is in base 2.
What am I misunderstanding?
Thank you all so much in advance,
- vr0n
Homework Statement
The question is this: Find the best Big-O function for the function |n + 2| − |n / 3|.
And here are the options (all logs are in base 2):
1. log(n)
2. n3
3. n
4. n2
5. n4
6. n * log(n)
I should state here that what I inferred from this question was that the "best Big-O function" was the one that was the most closely bounded to the original function, so n20 would be an incorrect, through technically accurate, answer.
Homework Equations
Relevant equations are, of course, our given function: |n + 2| − |n / 3| (in the question, it is not referred to as f(n), but I will refer to it as this for ease of reference in the next equation)
And, the definition of Big Oh, which tells us that if for some constant c and some number k where all n>=k,
if |f(n)|<= c|g(n)| for all of n, then g is Big Oh of f.
The Attempt at a Solution
By finding the least common denominator, we can write |n + 2| − |n / 3| as 2n/3 + 2 (since we are interested in what is going on as n becomes large, and when n = 0, the function is positive -- with an answer of 2 -- I expected combining these functions would be fine. This may be where the issue arose, however, if that's the case it is still unclear to me why this would be wrong).
Now, if we ignore constants, we can write this is 2n/3. Since, for all n>=k when k = 0 and when c = 1, it is the case that |2n/3|<= 1|n|, I determined that the best answer for this was n (also, since the equation moves in a linear way, this made sense by inspection before working this out).
This was incorrect and I was informed the correct answer was log(n) where the log is in base 2.
What am I misunderstanding?
Thank you all so much in advance,
- vr0n