Difference between revisions of "TADM2E 2.23"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
(Undo revision 1178 by FuckyouMatt (talk))
 
(One intermediate revision by one other user not shown)
(No difference)

Latest revision as of 20:13, 4 August 2020

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) $.