Big O and Θ question, mostly needs checking

[SpiffyEh]

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

 

[KataKoniK]

.

Hi there,

Let me try to explain each question and provide some insight on your answers:

a) Yes, you are correct. Since big O notation is an upper bound, it is possible for an algorithm to have a worst-case time complexity of O(n^2) and still have some inputs that have a time complexity of O(n). This is because the worst-case time complexity is just the upper limit, and there could be inputs that do not trigger the worst-case scenario.

b) Your answer is correct. If an algorithm has a worst-case time complexity of O(n^2), then it is not possible for all inputs to have a time complexity of O(n). This is because if all inputs had a time complexity of O(n), then the worst-case time complexity would also be O(n) instead of O(n^2).

c) In this case, the algorithm has a tight bound of Θ(n^2), which means that it has a worst-case time complexity of n^2, but it could also have a best-case time complexity of n^2. Therefore, it is not possible for the algorithm to have a time complexity of O(n) on some inputs, since O(n) is a lower bound.

d) Your answer is correct. If an algorithm has a tight bound of Θ(n^2), then it is not possible for it to have a time complexity of O(n) on all inputs, since O(n) is a lower bound.

e) Your approach is correct. You have shown that the function f(n) is bounded by two functions - 100n^2 and 20n^2. Therefore, it falls within the range of Θ(n^2).

I hope this helps clarify your understanding of these questions. Good luck with your studies!