Big-O and Θ Questions Homework: Answers Explained

[Smish]

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

 

[LCKurtz]

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)

That just says $O(n^2)$ isn't the best bound, but it is surely a correct bound.

c) needs help

Remember $\Theta(n^2)$ is sharp. So the answer to c depends on whether it might be possible to use $\Theta(n)$ in this case. What do you think?

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)

Correct. Unlike the situation for $O(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

Once you understand c and d, I think you will see the answer to e is very easy.

 

[Smish]

I think I'm starting to get it.

So in c, having it take O(n) on some inputs would mean that it would have to be at least Ω(n). So it couldn't be Θ(n^2). And if that's correct I think I know how to solve question d.

Thank you for the help by the way.

 

[LCKurtz]

I think I'm starting to get it.

So in c, having it take O(n) on some inputs would mean that it would have to be at least Ω(n). So it couldn't be Θ(n^2). And if that's correct I think I know how to solve question d.

Thank you for the help by the way.

But if it is worst case $\Theta(n^2)$ that means it has lots of terms like $n^2$ or the theta order would be less.

 

[Smish]

But if it is worst case $\Theta(n^2)$ that means it has lots of terms like $n^2$ or the theta order would be less.

I see. So I'm taking another crack at e again.

From what I understand, for the even f(n) = 100n^2 the Θ(n^2) holds true because all the terms in this are to the power of n^2. However for the odd f(n) = 20n^2 − n log2 n the O(n^2) holds true but the Ω(n^2) doesn't hold true because of the n log2 n. Since f(n) isn't both Ω(n^2) and O(n^2), then it isn't Θ(n^2).

 

[LCKurtz]

I see. So I'm taking another crack at e again.

From what I understand, for the even f(n) = 100n^2 the Θ(n^2) holds true because all the terms in this are to the power of n^2. However for the odd f(n) = 20n^2 − n log2 n the O(n^2) holds true but the Ω(n^2) doesn't hold true because of the n log2 n. Since f(n) isn't both Ω(n^2) and O(n^2), then it isn't Θ(n^2).

I think you are getting it now.

 

[Smish]

I think you are getting it now.

Couldn't have gotten it without your help. Thank you so much for clarifying it.