16
votes
What is the meaning of $O(m+n)$?
Part 1
I'm going to do something I decided I wouldn't do: try to nutshell my research on this topic. I'll go over on how the algorithmic O-notation must be defined, why it is probably not what you've ...
- 431
11
votes
What is the meaning of $O(m+n)$?
Part 2
$$
\newcommand{\TR}{\mathbb{R}}
\newcommand{\TN}{\mathbb{N}}
\newcommand{\subsets}[1]{\mathcal{P}(#1)}
\newcommand{\setb}[1]{\left\{#1\right\}}
\newcommand{\land}{\text{ and }}
$$
Algorithms
...
- 431
8
votes
Accepted
What is the "continuity" as a term in computable analysis?
Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example:
...
- 3,213
8
votes
What is the "continuity" as a term in computable analysis?
Arno's answer provides some very useful background reading material, I would just like to address your specific question about $\mathbb{R}$.
Let us first recall a result by Peter Hertling, see Theorem ...
- 31k
6
votes
Accepted
How does sum of first $k$ integers equal $k(k+1)/2$
Let me tell you the story of young Carl Friedrich Gauss.
He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he ...
- 31.5k
6
votes
Accepted
How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?
Let $S(n) = T(n) - 2n - 2$. You can check that $S(n) = S(n-1) + S(n/2)$ (ignoring the fact that $n/2$ need not be an integer). This shows that the additive $n$ term doesn't make a big difference.
For ...
- 279k
5
votes
Accepted
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so
$$
g(n) \geq \...
- 279k
5
votes
Can someone explain why there are two summations here?
And why are they exactly the same? I showed a math professor and he
thinks they're labelled wrong but couldn't figure it out. I don't even
get why there are two.
When in doubt, check the book's ...
- 1,493
4
votes
Accepted
Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?
If you picture these as distances along a road, it should be very intuitive.
If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you ...
- 713
4
votes
Accepted
Do formulas involving fewer repetitions of variables give higher numerical precision?
First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point. For example, ...
- 12.1k
4
votes
Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1) $
Since $c^0=1$, you can re-write your function in the following way:
$$f(n)=\sum_{i=0}^n c^n \ .$$
That said, in order to prove that $f(n)=\Theta(1)$, you have to show that $f(n)$ is both $\Omega(1)$ ...
- 1,294
3
votes
Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?
First, let us note that for monotone $f$, the statement holds for some $c > 1$ iff it holds for all $c > 1$. Indeed, let $1 < c_1 < c_2$. If the statement holds for $c_2$ then $f(c_1n) \...
- 279k
3
votes
Complexity of computing the antiderivative of a given function
Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations
are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the ...
- 279k
3
votes
What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph?
I've only ever heard of directed and undirected graphs, whose definitions can be found in Wikipedia. Rudimentary search reveals the following interpretations of unidirectional and bidirectional graphs;...
- 279k
3
votes
Accepted
Set of all rational numbers less than given computable real number is decidable
I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$.
If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between ...
- 14.6k
3
votes
Hash function to hash 6-digit positive integers
I think you've missed the point of hash tables. Hash tables are used to give array-like access to a dataset that's too big and sparse to store in an array. So, for example, it sounds like you're ...
- 82.1k
3
votes
Hash function to hash 6-digit positive integers
A hash function cannot avoid collisions when the size $M$ of the hash table is smaller than the size of the universal set $U$ that you are hashing. This is a consequence of the compression step. In ...
- 3,744
3
votes
Hash function to hash 6-digit positive integers
A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that ...
- 31.5k
3
votes
Can most programs (except the IO part) be re-written as a sequence of matrix operations?
If you regard the output of a program as a function of its input then matrices can be used to represent some programs, namely those where the output is a linear function of the input. So a program ...
- 1,589
3
votes
Why postfix is used more often than prefix expression?
The evaluation is easier for postfix-notation expressions.
The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time:
operand -> put it on ...
- 131
3
votes
Decryption of RSA
You'll need to factor the base of the RSA public key to be able to decrypt. That is the whole point: cracking RSA is equivalent to factoring, and factoring is (presumed to be) very hard.
- 14.1k
3
votes
Accepted
Precise algorithm for finding higher order derivatives
The first thing you should understand is why central differencing gives you a more precise solution.
Consider the Taylor expansion of $f$ around $x$:
$$f(x + h) = f(x) + h f'(x) + \frac{1}{2} h^2 f''(...
- 23.1k
3
votes
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
Here are the first few values of the expression $\sum_{k=1}^n (-1)^k k$, starting with $n = 1$:
$$ -1, 1, -2, 2, -3, 3, -4, 4, -5, 5,\ldots$$
Hopefully you can spot the pattern.
- 279k
3
votes
Accepted
Finding an approximate double-zero using binary search
This paper studies a similar problem: finding an approximate fixed-point of a two-dimensional function from the unit square to itself, which is accessible via value queries. The authors prove that ...
- 6,164
2
votes
Accepted
Derivative for x-direction for image
From my understanding, you are asking about computing the derivative, at some pixel $(x,y)$, with respect to the $x$ direction. We can approximate a derivative of some function $f(x,y)$ along the $x$ ...
- 453
2
votes
Accepted
Reference request: Introduction to reinforcement learning with hand calculation examples
Poole and Mackworth's Artificial Intelligence: Foundations of Computational Agents, fully available online, has one such example for Q-learning.
Sutton & Barto's Reinforcement Learning: An ...
- 171
2
votes
Are the functions always asymptotically comparable?
For completeness, here's a slightly easier version of Ambroz's answer. Not only is it strictly increasing, but smooth as well!
Intuitively, we want to construct a function that oscillates between fast-...
- 121
2
votes
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
Let n be the size of the array. Let k = log2 (n). At the first step, you divide by k. As long as the array size is more than $n^{1/2}$, you divide by more than k/2. I'd say this is O (log n / log log ...
- 31.5k
2
votes
What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
Seems that you are refering to iterated logarithm, also know as the $log *$ function. It is a function that expresses how many times you can take the logarithm of a number until it produces a number ...
- 1,212
Only top scored, non community-wiki answers of a minimum length are eligible