Difference between revisions of "TADM2E 2.23"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
=2-23.= | =2-23.= | ||
| − | == If I prove that an algorithm takes | + | == If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? == |
Answer: Yes. | Answer: Yes. | ||
| Line 8: | Line 8: | ||
Explanation: | Explanation: | ||
| − | + | <math>O(n^2)</math> worst-case means that the worst-case is bound from above by <math>O(n^2)</math>; it does not necessarily mean that all cases must follow that complexity. Thus, there could be some inputs that are <math>O(n)</math>. | |
| − | == If I prove that an algorithm takes | + | == If I prove that an algorithm takes <math>O(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? == |
Answer: Yes. | Answer: Yes. | ||
| Line 18: | Line 18: | ||
Explanation: | Explanation: | ||
| − | + | <math>O(n^2)</math> worst-case is only an upper bound on the worst-case. It is possible that all inputs can be done in <math>O(n)</math>, which still follows this upper bound. | |
| − | == If I prove that an algorithm takes | + | == If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''some'' inputs? == |
Answer: Yes. | Answer: Yes. | ||
| Line 28: | Line 28: | ||
Explanation: | Explanation: | ||
| − | Although the worst case is | + | Although the worst case is <math>\Theta(n^2)</math>, this does not mean all cases are <math>\Theta(n^2)</math>. |
| − | == If I prove that an algorithm takes | + | == If I prove that an algorithm takes <math>\Theta(n^2)</math> worst-case time, is it possible that it takes <math>O(n)</math> on ''all'' inputs? == |
Answer: No. | Answer: No. | ||
| Line 38: | Line 38: | ||
Explanation: | Explanation: | ||
| − | The worst-case input must follow | + | The worst-case input must follow <math>\Theta(n^2)</math>, so it can't be <math>O(n)</math>. Therefore, all cases are not <math>O(n)</math> |
| − | == Is the function | + | == Is the function <math>f(n) = \Theta(n^2)</math>, where <math>f(n) = 100n^2</math> for even <math>n</math> and <math>f(n) = 20n^{2} - n * log_2 n</math> for odd <math>n</math>? == |
Answer: Yes. | Answer: Yes. | ||
| − | Explanation: Both even and odd functions are | + | Explanation: Both even and odd functions are <math>\Theta(n^2)</math>. |
Revision as of 18:23, 11 September 2014
Contents
- 1 2-23.
- 1.1 If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?
- 1.2 If I prove that an algorithm takes $ O(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?
- 1.3 If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on some inputs?
- 1.4 If I prove that an algorithm takes $ \Theta(n^2) $ worst-case time, is it possible that it takes $ O(n) $ on all inputs?
- 1.5 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 $?
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) $.
