- #1

- 20

- 0

## 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. n

^{3}

3. n

4. n

^{2}

5. n

^{4}

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 n

^{20}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