## Exercises - Analysis of Algorithms

1. Give the Tilde approximations for the following functions:

1. $1/n + 1$
2. $7n^8 + 3n - 4$
3. $5n + 4n \log n$

1. $1$
2. $7n^8$
3. $4n \log n$

2. Prove that $C(n) = 3n^3 + 2n + 7$ is $\Theta(n^3)$. You may assume $n \ge 1$.

Given that $n \ge 1$, it must be the case that $C(n) = 3n^3 + 2n + 7 \le 3n^3 + 2n^3 + 7n^3 = 12n^3$. Further, $C(n) = 3n^3 + 2n + 7 \ge n^3$ for all positive $n$. Hence $|n^3| \le C(n) \le 12|n^3|$, so $C(n)$ is $\Theta(n^3)$.

3. Show that the function $C(n) = n^3 + 20n + 1$ is not $O(n^2)$.

We argue indirectly. Suppose $C(n)$ is $O(n^2)$. Then there exists some constant $k$ such that for sufficiently large $n$ we always have $C(n) \le k \cdot n^2$. This means that $n^3 + 20n + 1 \le k \cdot n^2$. However, dividing both sides by $n^2$ quickly shows this is impossible as it gives $$n + \frac{20}{n} + \frac{1}{n^2} \le k$$ To see this, note that as $n \rightarrow \infty$ left side grows without bound, while the right side is constant. Having reached a contradiction, we have shown that $C(n)$ can not possibly be $O(n^2)$.

4. Show that the function $C(n) = n^3 + 20n$ is $\Omega(n^2)$.

Recall, $C(n)$ is $\Omega(n^2)$ if there is some constant $k$ such that $C(n) \ge k \cdot n^2$ for sufficiently large $n$. Disregarding $n=0$, note $n^3 + 20n \ge k \cdot n^2$ and $n + 20/n \ge k$ are equivalent. Further, the latter inequality always holds for a sufficiently large $n$ as the left side of the inequality grows without bounds as $n$ increases (for sufficiently large $n$), while the right side is constant.

5. Find the cost function (associated with time complexity) for the indicated primitive operation of interest.

function(int n) {
if (n==1)
return;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++)
{
print("*"); //<-- primitive operation of interest
break;
}
}
}

Note that even though the inner loop continuation condition is j<=n, its body executes only once due to the break statement. Hence, $C(n) = n$

6. Find the cost function (associated with time complexity) for the indicated primitive operation(s) of interest, and the corresponding tilde approximation. Assume $n$ is even.

int count = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = 0; j < n; j++)
count++;  // <-- primitive operation of interest
}
else {
for (int j = 0; j < 10; j++)
count++;  // <-- primitive operation of interest
}
}

$\displaystyle{C(n) = \frac{n^2}{2} + 5n \sim \frac{n^2}{2}}$

7. Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation. Assume $n$ is even.

int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < 2*n; j++) {
count++;  // <-- primitive operation of interest
}
}

$\displaystyle{C(n) = \frac{3n^2}{2} + \frac{n}{2} \sim \frac{3n^2}{2}}$

8. Find the cost function (associated with time complexity) for the indicated primitive operation of interest. For simplicity, assume $n$ is a positive integer power of 2.

int count = 0;
for (int i = n/2; i < n; i++)
for (int j = 1; j < n; j = 2*j)
for (int k = 1; k < n; k *= 2)
count++;  // <-- primitive operation of interest

Note that the innermost and second innermost loops both execute $\sim \log_2 n$ times, while the outer loop executes $n/2$ times. Thus, the cost function here is $C(n) \sim (n/2) \log_2^2 n$.

9. Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation. For simplicity, assume $n$ is a positive integer power of 2.

int count = 0;
for (int i = n/2; i <= n; i++)
for (int j = 1; j + n/2 <= n; j++)
for (int k = 1; k <= n; k = k*2)
count++; // <-- primitive operation of interest

The inner-most loop executes $(\log_2 n + 1)$ times, while the middle loop executes $n/2$ times, and the outer loop executes $(n/2 + 1)$ times. Thus,

$$C(n) = \left( \frac{n}{2} + 1 \right) \left( \frac{n}{2} \right)(\log_2 n + 1) \sim \frac{n^2 \log_2 n}{4}$$
10. Use Tilde notation to express the running time associated with the indicated primitive operation of interest. (For the ambitious -- find a formula for the exact value of the cost function for any integer $n$.)

int i = 1;
int s = 1;
while (s <= n) {
i++;
s += i;
print("*"); // <-- primtive operation of interest
}

Note that the primitive operation of interest happens as many times as $s$ is increased. Suppose this happens $C(n)=k$ times.

Then, we can relate $n$ and $k$ together by considering the value of $s$: $$s = 1 + 2 + 3 + \cdots + k \le n < 1 + 2 + 3 + \cdots + k + (k+1)$$

Collapsing the sums on either side, we have: $$\frac{k(k+1)}{2} \le n < \frac{(k+1)(k+2)}{2}$$ We want $k$ in terms of $n$, and so let us eliminate the denominators by multiplying by $2$: $$k(k+1) \le 2n < (k+1)(k+2)$$ At this point we can argue that $C(n) \sim \sqrt{2n}$, given that both $k(k+1)$ and $(k+1)(k+2)$are $\sim k^2$, provided $C(n)=k$ is a function that increases without bound -- which it does here.

Interestingly in this situation, one can predict the exact value of the cost function for any $n$. To see this, note that we can solve $k(k+1) <= 2n$ for $k$ (which must be a positive integer) to obtain $$k <= \frac{-1 + \sqrt{1+8n}}{2}$$ Similarly, we can solve $(k+1)(k+2) > 2n$ to find $$k > \frac{-3 + \sqrt{1+8n}}{2}$$ Thus, $$\frac{-3 + \sqrt{1+8n}}{2} < C(n) \le \frac{-1 + \sqrt{1+8n}}{2}$$ (We pause here to note that one could use the squeeze theorem from calculus to establish $\lim_{n \rightarrow \infty} C(n) = \sqrt{2n}$, which further validates that $C(n) \sim \sqrt{2n}$.)

Finally, note that the interval of possible values for $C(n)$ described by this last string inequality is exactly one unit wide. As $C(n)$ must be an integer (as it counts the frequency of execution for our primitive operation), $C(n)$ must be the unique integer contained in this interval.

Appealing to the floor function, we can then write a formula for $C(n)$: $$C(n) = \left \lfloor \frac{-1 + \sqrt{1+8n}}{2} \right \rfloor$$