# Asymptotic Notation

## Problem 1

Prove using the formal definitions of $O$, $\Omega$, and $\Theta$:

a. $3n^{2} + 7n + 3 \in O(n^{2})$

By definition of $O(n^{2})$, for some $c > 0$:
$$0 \leq 3n^{2} + 7n + 3 \leq cn^{2}$$
$$0 \leq 3n^{2} \leq cn^{2}$$
Lower order terms ($7n + 3$) can be dropped since limiting behavior is dictated by highest degree terms (which can be demonstrated by the application of L'Hopital's Rule). Thus, the relation is trivially satisfied for $c \gg 3$, and thus $3n^{2} + 7n + 3 \in O(n^{2})$.

b. $n^{2} + n + 9 \not\in O(n)$

Assume for contradiction that $n^{2} + n + 9 \in O(n)$ By definition of $O(n)$, for some $c > 0$:
$$0 \leq n^{2} + n + 9 \leq cn$$$$0 \leq n^{2} \leq cn$$
Lower order terms ($n + 9$) can be dropped since limiting behavior is dictated by highest degree term. There is no $c$ that can satisfy this equation, given that dividing $n^{2} \leq cn$ by $n$ yields $n \leq c$, it must be that $n^{2} + n + 9 \not\in O(n)$.

c. $25n^{3} - n^{2} \in \Theta (n^{3})$

To show $25n^{3} - n^{2} \in \Theta (n^{3})$ is to show the existance of some positive constants $c_{1}, c_{2}$, and $n_{0}$ such that $0 \leq c_{1}n^{3} \leq 25n^{3} - n^{2} \leq c_{2}n^{3}~~\forall n \geq n_{0}$. Proceed as follows:
$$n^{-3} * \{c_{1}n^{3} \leq 25n^{3} - n^{2} \leq c_{2}n^{3}\}$$$$c_{1} \leq 25 - n^{-1} \leq c_{2}$$
Let $n_{0} = 1$ which allows that for any $c_{1}$ and $c_{2}$ satisfying the relation $c_{1} \leq 24 \leq c_{2}$ the statement $0 \leq c_{1}n^{3} \leq 25n^{3} - n^{2} \leq c_{2}n^{3}~~\forall n \geq 1$ to become a valid one.
Hence, $25n^{3} - n^{2} \in \Theta (n^{3})$.

d. Disprove $f \in O(g) \rightarrow f \in \Theta (g)$

Let $f(n) = n$ and $g(n) = n^2$. Then $f=O(g)$ but $f\neq\Omega(g)$

## Problem 2

Give the asymptotic running time of the following code segments in $\Theta$ notation.

function squareAll(data) { for(var i = 0; i < data.length; i++) { data[i] = data[i] * data[i]; } return data; }

A simple iteration over every element of an array is $\Theta(n)$.

function squarePlusOne(data) { data = squareAll(data); for(var i = 0; i < data.length; i++) { data[i] += 1; } return data; }

The call to

`squareAll`

has a run time of $\Theta(n)$, and then this function has a loop which adds another $\Theta(n)$. To find the run time of this code segment, we simply add them together. This means we have $\Theta(2n)$ which is still just $\Theta(n)$ – constants are ignored.For the following code segments, assume `image`

is an array of length $n^2$ (e.g. both its width and height are n). Give both worst case and best case (if applicable).

function getRegion(image, start_x, start_y, regWidth, regHeight) { var pixels = []; for(var y = 0; y < regHeight; y++) { for(var x = 0; x < regWidth; x++) { var pixel = image.getPixel(start_x + x, start_y + y); pixels.push(pixel); } } return pixels; }

Focusing on the loops, the inner loop (

Since we enter the inner loop for every iteration of the outer loop, we're repeating a $O(n)$ code segment a $\Theta(n)$ number of times. So the run time of this function is $\Theta(n^2)$. More generally, its $\Theta(width * height)$.

`for(var x = 0; x < regWidth; x++)`

) is a simple linear scan which is $\Theta(regWidth)$ or just $\Theta(n)$ in this case. Similarly, the outer loop is `for(var y = 0; y < regHeight; y++)`

and so we have $\Theta(height)$ or $\Theta(n)$.
Since we enter the inner loop for every iteration of the outer loop, we're repeating a $O(n)$ code segment a $\Theta(n)$ number of times. So the run time of this function is $\Theta(n^2)$. More generally, its $\Theta(width * height)$.

function createTilesheet(image, tileWidth, tileHeight) { var result = []; for(var y = 0; y < image.height; y += tileHeight) { for(var x = 0; x < image.width; x += tileWidth) { var tile = getRegion(image, x, y, tileWidth, tileHeight); result.push(tile); } } return result; }

The call to

There's small problem with that though, the indices increase by

In essence this is just a linear scan through a 2D array, and its pretty much the same as

`getRegion`

makes this a little tricky, since `getRegion`

was shown to be $\Theta(n^2)$, and the loop seems like its going to multiply this by $\Theta(n^2)$ which will yield $\Theta(n^4)$.
There's small problem with that though, the indices increase by

`tileHeight`

and `tileWidth`

respectively, so the number of times `getRegion`

is called is $(width / tileWidth) * (height / tileHeight) = \frac{width * height}{tileWidth * tileHeight}$. Multiplying this with the time complexity of `getRegion`

we get $\frac{width * height}{tileWidth * tileHeight} * (tileWidth * tileHeight) = width * height$.
In essence this is just a linear scan through a 2D array, and its pretty much the same as

`getRegion`

(which does all the work in this function). Hence, this function is $\Theta(n^2)$.