Some Useful Facts

Some handy results

In this lesson, we discuss four results that are useful to know. Note that the size of input for an algorithm is always some discrete value. That’s the reason these results are proven here for integer values of $n$ only and not real values of $n$.

In fact, $2^n$ is a strict upper bound on $n$, for any integer $n$.

$$n \lt 2^n\ \ \text{ for all }n \geq 1$$

It’s clearly true for $n=1$, but it’s also true for larger values as for every unit increase in the value of $n$, the left-hand side (LHS) increases by $1$, but the right-hand side (RHS) doubles.

Here’s another well-known fact.

Once again, we can say something stronger:

$$\log_2 n < n\ \ \ \text{ for all }n \geq 1$$ ...