TADM2E 2.23

From Algorithm Wiki
Revision as of 20:13, 4 August 2020 by Matt (talk | contribs) (Undo revision 1178 by FuckyouMatt (talk))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

2-23.

If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?

Answer: Yes.


Explanation:

$ O(n^2) $ worst-case means that the worst-case is bound from above by $ O(n^2) $; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are $ O(n) $.


If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?

Answer: Yes.


Explanation:

$ O(n^2) $ worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in $ O(n) $, which still follows this upper bound.


If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?

Answer: Yes.


Explanation:

Although the worst case is $ \Theta(n^2) $, this does not mean all cases are $ \Theta(n^2) $.


If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?

Answer: No.


Explanation:

The worst-case input must follow $ \Theta(n^2) $, so it can't be $ O(n) $. Therefore, all cases are not $ O(n) $


Is the function $ f(n) = \Theta(n^2) $, where $ f(n) = 100n^2 $ for even $ n $ and $ f(n) = 20n^{2} - n * log_2 n $ for odd $ n $?

Answer: Yes.


Explanation: Both even and odd functions are $ \Theta(n^2) $.