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