# TADM2E 2.23

## 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 $?

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

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