| | |
Give the Tilde approximations for the following functions:
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)$.
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)$.
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.
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$
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}}$ (for even $n$), and for the curious...
$\displaystyle{C(n) = \frac{n^2 + 11n - 10}{2} \sim \frac{n^2}{2}}$ (for odd $n$)
Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation.
for (int i = 0; i < n; i++) {
for (int j = n; j > i+1; j--) {
System.out.println("plus"); // primitive operation
System.out.println("minus"); // primitive operation
}
}
$C(n) = n^2 - n \sim n^2$
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}}$
Find the cost function (associated with time complexity) for the indicated primitive operations of interest, and the corresponding tilde approximation. Assume $n$ is even.
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n/2; j++) {
System.out.println("fee"); // primitive operation of interest
System.out.println("fi"); // primitive operation of interest
}
}
$\displaystyle{C(n) = \frac{n^2}{4} - \frac{n}{2} \sim \frac{n^2}{4}}$
Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation. Assume $n = 2^k$ for some positive integer $k$.
for (int i = n/2; i < n; i *= 2) {
System.out.println("fo fum"); // primitive operation of interest
}
$\displaystyle{C(n) = 1 \sim 1}$
Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation. Assume $n=2^k$ for some positive integer $k$.
for (int i = 1; i < n/4; i *= 2) {
System.out.println("stop short"); // primitive operation
}
for (int i = 0; i < 2*n; i += 2) {
System.out.println("more stuff"); // primitive operation
}
$n + \log_2 n - 2$
Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation.
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
for (int k = j+1; k < n; k++)
count++; // primitive operation of interest
$\displaystyle{C(n) = \frac{n(n-1)(n-2)}{6} \sim \frac{n^3}{6}}$.
Interestingly, you can express this with combinations (i.e., $C(n) = {}_n C_3$) as each combination of $3$ values taken from the group of $n$ values between $0$ and $(n-1)$ inclusive, is encountered once (where $i$, $j$, and $k$ are these values in ascending order, respectively.
In case you are rusty with combinations, remember that ${}_n C_k$ counts the number of groups of $k$ items you can choose from a group of $n$ items. (order doesn't matter -- just who is in the group). The formula for finding this count is given by $${}_n C_k = \frac{n!}{k! (n-k)!}$$Find the cost function (associated with time complexity) for the indicated primitive operation of interest, and the corresponding tilde approximation. Assume that $n = 3^k$ for some positive integer $k$
for (int i = 1; i < n; i++) {
count++; // primitive operation of interest
}
for (int j = 1; j < n; j *= 3) {
count++; // primitive operation of interest
}
$\displaystyle{C(n) = n + \log_3 n - 1 \sim n}$.
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$.
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}$$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$$
In each table below, the execution times of a related snippet of code is found for various values of $n$ (the "problem size"), these times are given by the value of $C(n)$ in the corresponding row of the table below. For convenience, the value of $C(2n)/C(n)$ is also given for all but the last row. Assuming $C(n) \sim k n^p$ for some constant $k$ and integer $p$, what does $p$ appear to be in each case?
$\displaystyle{\begin{array}[t]{|c|c|c|}\hline n & C(n) & C(2n)/C(n)\\\hline 4 & 10 & 2.1\\\hline 8 & 21 & 5.57\\\hline 16 & 117 & 7.31\\\hline 32 & 855 & 7.70\\\hline 64 & 6584 & 7.92\\\hline 128 & 52144 & 7.98\\\hline 256 & 416112 & \vdots \\\hline \end{array}}$
$\displaystyle{\begin{array}[t]{|c|c|c|}\hline n & C(n) & C(2n)/C(n)\\\hline 4 & 10 & 2.2\\\hline 8 & 22 & 8.56\\\hline 16 & 188 & 11.29\\\hline 32 & 2126 & 14.70\\\hline 64 & 31254 & 15.59\\\hline 128 & 487252 & 15.97\\\hline 256 & 7781418 & \textrm{etc.} \\\hline \end{array}}$
Using "doubling time" analysis, we expect for large $n$ and a cost function of $C(n) \sim k n^p$ that $C(2n)/C(n)$ approach $2^p$. In part (a), this fraction appears to approach $2^3 = 8$ in the table, suggesting that $p = 3$. In part (b), this fraction appears to approach $2^4 = 16$, suggesting $p = 4$.