# TADM2E 2.23

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