CODEWITHSUNDEEP
algorithmsortingruntimebig-o
Ryan Fasching
Ryan Fasching

Reputation: 541

Can someone explain why these running times are right for this?

An algorithm runs in time n^2 + 3n + 5 for all inputs of size greater or equal to 500 and in time 2^(2n) for all input sizes less than 500. Select all the true statements from below:

1: Its running time is O(2^(n))
2: Its running time is O(n^(2))
3: Its running time is Θ(n^(2))
4: Its running time is Θ(2^(2n))
5: Its running time is O(4^(n))
6: Its running time is Ω(n^(2))

the right answers are: 1, 2, 3, 5, 6

I have no idea how all of these can be answers to the problem above, please help!

Upvotes: 0

Views: 63

Answers (1)

templatetypedef
templatetypedef

Reputation: 372832

Remember that big-O notation only talks about the behavior of a function in the long term. Look back at the definition:

f(n) = O(g(n)) if there are numbers n0 and c such that for any n ≥ n0, we have f(n) ≤ c·g(n).

In the case of your function, your function behaves one way for "small" inputs and one way for "large" inputs. Big-O notation will only really consider the "large" case, so you can show that your function is O(n2), because for any n ≥ 500, we have

f(n) = n2 + 3n + 5 ≤ 5n2.

The definition of big-Ω works the same way - it only considers "sufficiently large" inputs, so you can say that your function is Ω(n2) because for any n ≥ 500, we have

f(n) = n2 + 3n + 5 ≥ n2.

So that means that your function is Θ(n2) as well.

So what about those other answers? Well, any function that's O(n2) is also O(4n) because big-O notation is an upper-bound, not a tight bound. It's not, however, Θ(4n), because the function isn't Ω(4n) since 4n grows dramatically faster than n2 long term.

Upvotes: 1

Related Questions