# Tag Info

### 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

### 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
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

### 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
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
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
Accepted

• 23.1k

### 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
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
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
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

### 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-...
### 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 ...
### 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 ...