- #1

- 194

- 0

## Homework Statement

For each of these questions, briefly explain your answer.

(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?

## Homework Equations

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