Difference between revisions of "TADM2E 2.23"
(Recovering wiki) 
(No difference)

Revision as of 18:14, 11 September 2014
Contents
 1 223.
 1.1 If I prove that an algorithm takes <math>O(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on some inputs?
 1.2 If I prove that an algorithm takes <math>O(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on all inputs?
 1.3 If I prove that an algorithm takes <math>\Theta(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on some inputs?
 1.4 If I prove that an algorithm takes <math>\Theta(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on all inputs?
 1.5 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>?
223.
If I prove that an algorithm takes <math>O(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on some inputs?
Answer: Yes.
Explanation:
<math>O(n^2)</math> worstcase means that the worstcase 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 <math>O(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on all inputs?
Answer: Yes.
Explanation:
<math>O(n^2)</math> worstcase is only an upper bound on the worstcase. 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 <math>\Theta(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on some inputs?
Answer: Yes.
Explanation:
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 <math>\Theta(n^2)</math> worstcase time, is it possible that it takes <math>O(n)</math> on all inputs?
Answer: No.
Explanation:
The worstcase 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 <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.
Explanation: Both even and odd functions are <math>\Theta(n^2)</math>.