(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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?

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Big O and Θ question, mostly needs checking

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**