Week 11: Harder Time Complexity Problems

           There is no class this week so for fun, we go over a few harder time complexity problems.  Consider the sequences $f(n) = n^4 - 165n^3 - 240n^2 - 265n - 373$ and  $g(n) = 157n^3 + 257n^2 + 337n + 457$.

Problem 1: Show that $f \notin O(g)$ without using any limit definitions.

Problem 2:  Show that $f \in \Omega (g)$ without using any limit definitions.

Problem 1 Tips:

            The definition that we have is $f \in O(g)$, which is defined as:

$\exists c \in R^+, \exists B \in N, ( \forall n \in N, n \geq B \implies f(n) \leq g(n))$.

Thus, its negation is:

$\forall c \in R^+, \forall B \in N, ( \exists n \in N, n \geq B \wedge f(n) > g(n))$.

We must choose $n$.  Using the recommended strategies of my instructors, we get:

$n^4 - 165n^3 - 240n^2 - 265n - 373 \geq$

$n^4 - 1043n^3$

$???$

$c(1208n^3) \geq$

$c(157n^3 + 257n^2 + 337n + 457)$.

The $???$ part indicates the area where the strategies of my instructors do not cover.  So I think hard here (like really hard) and I come up with this.  All we must do is find a $n$ that satisfies the inequality $n^4 - 1043n^3 > c(1208n^3)$.  We have:

$n^4 - 1043n^3 > c(1208n^3)$

Move $-1043n^3$ on the left side to the right and factor out $n^3$ from the resulting right:

$n^4 > n^3(c1208 + 1043)$

It looks like we will choose $n > 0$.  That way, we can divide both sides by $n^3$:

$n > c1208 + 1043$.

Our choice of $n$ is then $max(\lceil c1208 + 1043 \rceil + 1, B)$.

Problem 2 Tips:

            Likewise, we show that $f \in \Omega (g)$, which is defined as:

$\exists c \in R^+, \exists B \in N, ( \forall n \in N, n \geq B \implies f(n) \geq g(n))$.

We must choose $c, B$.  We have a similar inequality to problem 1:

$n^4 - 1043n^3 \geq 1208n^3$

Again, we choose $B >0$ so that we can divide both sides by $n^3$.  Then add both sides by $1043$ to yield:

$n \geq 2051$.

Of course, to choose $B = 2051$, we must choose $c = 1$.  Otherwise, the first step is irreversible.