117
I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones.
Computer Graphics/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, heavily! If you go down this path, you may also want to ...
33
You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.
Simply speaking, since
$$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$
you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent ...
25
Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell.
Curiously, it also seems that most ...
21
Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and
$$
g(n) = \begin{cases}
1 & \text{if $n$ is odd},
\\\
n^2 & \text{if $n$ is even}.
\end{cases}
$$
Moreover, functions like $g(n)$ do actually arise as running times of algorithms. Consider the obvious brute-force algorithm to determine ...
20
This is somewhat obscure, but calculus turns up in algebraic data types. For any given type, the type of its one-hole contexts is the derivative of that type. See this excellent talk for an overview of the whole subject. This is very technical terminology, so let's explain.
Algebraic Data Types
You may have come across tuples being referred to as product ...
15
It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.
This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. ...
15
Recall that for $k > 1$, by definition we have $\log^*k = \log^*(\log{k}) + 1$.
By applying the definition twice, we see that $\log^*(2^{2^n}) = \log^*n + 2$. Now we can compare $\log^*n + 2$ and $(\log^*n)^2$.
14
Do what you did, but let $a = (3^{0.2})$... that should do it, right?
The reason that what you did didn't work is as follows. The big-oh bound is not tight; while the logarithm to the fifth is indeed big-oh of linear functions, it is also big oh of the fifth root function. You need this stronger result (which you can also get from the theorem) to do what ...
14
Rotations: that arise in Computer Graphics and Robotics , through rotation matrices, Quaternions, etc.
Cordics for computing these functions on a Microprocessor / FPGA
Transforms in Image Compression and elsewhere , e.g. FFT computation in $O(n \log n)$ time
Anything to do with the interface between CS and Signal Processing
Pretty much anywhere in ...
13
Automation - Similar to robotics, automation can require quantifying a lot of human behavior.
Calculations - Finding solutions to proofs often requires calculus.
Visualizations - Utilizing advanced algorithms requires calculus such as cos, sine, pi, and e. Especially when you're calculating vectors, collision fields, and meshing.
Logistics and Risk ...
12
Well, since this upper bound is not nearly tight, you can just use basic transformations to get
$$(n+1)!< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$
12
Numerical Methods. There exist cumbersome calculus problems that are unique to specific applications, and they need solutions faster than a human can practically solve without a program. Someone has to design an algorithm that will compute the solution. Isn't that the only thing that separates programmers from scientists?
11
At the suggestion of Raphael, I have turned a previous comment into this answer.
It is not true that $O(f(n)) \subset \Theta(f(n))$. In fact, $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$, by definition. So we have $\Theta(f(n)) \subset O(f(n))$.
11
You can compare ratios of adjacent values: $(n+1)!/n! = n+1$ versus $2^{2^n}/2^{2^{n-1}} = 2^{2^{n-1}}$. Since $n+1\leq 2^{2^{n-1}}$ for $n \geq 1$, you can prove using mathematical induction that $(n+1)! \leq 2^{2^n}$.
10
If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:
$f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$
Our recurrence is defined as ...
10
No, the constants $c_1,c_2$ are the same for all values of $n$. If they could depend on $n$ then the definition would be meaningless since $\Theta(g(n))$ would contain all positive functions. Indeed, suppose $f,g$ are two positive functions. Then for all $n$, $$c_1g(n) \leq f(n) \leq c_2g(n) \text{ for } c_1 = c_2 = \frac{f(n)}{g(n)}.$$
10
Not a rigorous proof, but a "from the top of my head" explanation.
Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.
To make sure the root ...
9
$\log n$ is the inverse of $2^n$. Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.
$n / \log n$ vs $n^k$, for $k < 1$ is identical to:
$n / \log n$ vs $n / n^{1-k}$
as $n^{1-k} > \log n$ for ...
9
Using de l'Hôpital's rule on discrete functions is meaningless; you would have to use continuous extension. For factorials, that would be the Gamma function. For discrete functions, there is Stolz–Cesàro.
In either case, considering difference or differential quotients does not make sense for (super)exponential functions: since growth is at least of the ...
8
The short answer to your question is "no". Richardson's theorem and its later extensions basically state that as soon as you include the elementary trigonometric functions, the problem of deciding if $f(x) = 0$ (and hence if $f(x) = g(x)$, since this is the same as $f(x) - g(x) = 0$) is unsolvable.
What's interesting about this is that the first-order ...
7
From wikipedia, definition of big O notation:
if and only if there is a positive constant M such that for all
sufficiently large values of $x$, $f(x)$ is at most M multiplied by $g(x)$
in absolute value. That is, $f(x) \in O(g(x))$ if and only if there exists
a positive real number $M$ and a real number $x_0$ such that
$|f(x)|<= M |g(x)| \quad ...
7
The total work is given by the sum of a geometric progression. In particular, let $r = a/b^d$, then total work = $O(n^d)\times (1+r+r^2+\ldots+r^p)$, where $p$ is the maximum depth.
Let $S = (1+r+r^2+\ldots+r^p)$.
If $r>1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.
If $r<1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.
7
Use a recursion tree (otherwise known as the proof of the Master Theorem). I'll assume here that $r>1$, since otherwise the recurrence never bottoms out.
The root of the recursion tree for $T(n)$ has value $nr^2$.
The root has $r^2$ children, each with value $(n/r)r^2 = nr$. Thus, the total value of all children is $nr^3$.
Each child has $r^2$ children ...
7
Let $a = 1$ and $b = 2$, so that
$$ T(2^n) = \sum_{k=0}^n f(2^k). $$
For case 3 to apply, we need $f(n) = \Omega(n^\epsilon)$ (for some $\epsilon > 0$) and the regularity condition, $f(n/2) \leq (1-\delta) f(n)$ (for some $\delta > 0$). You get the regularity condition from the proof, i.e. it's a proof-generated concept. While the regularity condition ...
7
[The reviews are based on my first hand experience with the materials.]
Quick Read:
Essentials of game theory
(Leyton-Brown, Shoham) - This is a ~100 page book, which will give a strong intuition (and more) on Game theory, this mostly covers the basics, the math here is also pretty lightweight, and this is very much readable (even by a college junior). ...
6
Yes, the answer is $\lg n \cdot \lg \lg n$:
Reason this out by expanding the recurrence and looking for a pattern:
\begin{align*}
T(n) &= 2T(\sqrt{n}) + \lg n \\
&= 2( 2T( \sqrt[4]{n} ) + \log(\sqrt{n}) ) + \lg n \\
&= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n \\
&= 4T( \sqrt[4]{n} ) + 2 \lg n \\
&=...
6
Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.
6
Here's a pair monotonic functions that are not asymptotically comparable. This is relevant because most complexities arising in practice are in fact monotonic.
$$ f(x) = \Gamma( \lfloor x \rfloor + 1 ) = \lfloor x \rfloor ! $$
$$ g(x) = \Gamma( \lfloor x-1/2 \rfloor + 3/2 ) $$
Here, $ \Gamma $ is the gamma function. The second function is specially ...
6
Computers don't use the hexadecimal number system for assembly language. Assembly language, or rather machine code, uses base 256 (typically): instructions are encoded in units of bytes. When displaying machine code, it is customary to use octal or hexadecimal. The reason is that in many cases, the byte is further subdivided into bitstrings, and identifying ...
6
Your problem seems to reduce the following simpler question:
Given two functions $F,G$ in class of functions, do we have $F(x)=G(x)$ for all $x$? (In other words, do they have the same value everywhere?)
I don't know whether this is decidable, for this class of functions. If it is, then your problem should be decidable as well.
For your problem, a ...
Only top voted, non community-wiki answers of a minimum length are eligible
