# Big O and Θ question, mostly needs checking

1. Sep 9, 2010

### SpiffyEh

1. The problem statement, all variables and given/known data

(a) If I prove that an algorithm takes O(n^2) worst-case time, is it possible that it
takes O(n) on some inputs?
(b) If I prove that an algorithm takes O(n^2) worst-case time, is it possible that it
takes O(n) on all inputs?
(c) If I prove that an algorithm takes Θ(n^2) worst-case time, is it possible that it
takes O(n) on some inputs?
(d) If I prove that an algorithm takes Θ(n^2) worst-case time, is it possible that it
takes O(n) on all inputs?
(e) Is the function f(n) = Θ(n^2), where f(n) = 100n^2 for even n and f(n) =
20n^2 − n log2 n for odd n?

2. Relevant equations

3. The attempt at a solution

I understand a few of these ( I think). Here's what I have so far:
a) Yes, because big O is an upper bound and O(n) is smaller than O(n^2) it is possible some inputs have a big O of O(n)
b) No, because if the worst case time is O(n^2) then some inputs must have O(n^2) if all the inputs had O(n) then the worst case would be O(n) instead of O(n^2)
c) needs help
d) if Θ(n^2) is the worst time its not possible it takes Θ(n) on all inputs, otherwise the worst case Θ would be Θ(n) rather than Θ(n^2)
e) i did c_2 * g(n) =< f(n) =< c_1 * g(n) where f(n) = 100n^2 for every even n
c_2 * n^2 =< 100n^2 =< c_1* n^2 which is true for certain n values, so its proven
for the odd part i did the same thing, since you can drop the lower terms i dropped the 2logn part and just had f(n)=20n^2, then did the same method. Is this correct?

I don't understand what to do for c, i know that Θ is a tight bound upper and lower so i don't know if Θ(n) is possible. Could someone please explain this to me? And if you have time could you please check my other answers? Thank you