29
votes
How can a computer run an infinite loop?
In a contemporary processor there is, among many other things, a register (digital electronic component to hold some bits) called the Program Counter (PC). It holds the memory address to the current ...
- 544
26
votes
Accepted
How can a computer run an infinite loop?
step 1: take a calculator
step 2: input a number
step 3: add 1 to the number
step 4: subtract 1 from the number
step 5: goto step 3
If you didn't eventually get tired or bored you would be ...
- 4,226
19
votes
Accepted
Why are loops faster than recursion?
The reason that loops are faster than recursion is easy.
A loop looks like this in assembly.
...
- 1,030
17
votes
Why are loops faster than recursion?
These other answers are somewhat misleading. I agree that they state implementation details that can explain this disparity, but they overstate the case. As correctly suggested by jmite, they are ...
- 11.9k
13
votes
Accepted
Looping and branching with Algorithmic Differentiation
AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be ...
- 246
10
votes
Accepted
From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?
Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:
Read the list in chunks of $k$, convert them ...
- 274k
10
votes
Does a do-while loop suffice for Turing-completeness?
I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.
do-while is equivalent to while-...
- 81.1k
7
votes
Loop variant for a while loop that occasionally doesn't decrease?
Just a hint for now, since this is a practice problem: consider a lexicographic combination of orders.
In some more detail: Suppose you have two maps $f_1:S\to D_1$ and $f_2:S\to D_2$ from your ...
- 2,158
6
votes
Loops at low level
When you are using vectorized operations in a high-level language such as Matlab or python, you are not avoiding loops, but rather pushing them from the high-level language (Matlab or python) to a low-...
- 274k
6
votes
How can a computer run an infinite loop?
At the most basic level, an "infinite loop" only requires two transistors — an astable multivibrator will alternate between two different digital states indefinitely as long as it has power. In some ...
- 319
6
votes
Accepted
Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model ...
- 29.5k
5
votes
Accepted
provability of while loop vs for loop
In a nutshell: What your teacher probably meant is that the semantics of while is pretty much the same in most languages, while the semantics of ...
- 19.3k
5
votes
Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?
Without fully answering your question, I would like to answer it at
least partially by remarking that computation cost can be evaluated
only with respect to an abstract model of computation.
If you ...
- 19.3k
5
votes
Do recursive algorithms generally perform better than their for-loop counterpart?
The answer will depend on the compiler. As @vonbrand wrote, "Given a good enough compiler, you might even get the very same object code." In particular, good compilers will do tail-call elimination. ...
D.W.♦
- 152k
5
votes
Looping and branching with Algorithmic Differentiation
If you want the derivative everywhere, automatic differentiation can't handle branches and loops. If you are satisfied with getting the derivative "almost everywhere", automatic differentiation might ...
D.W.♦
- 152k
5
votes
Accepted
Find Number of even subarrays $O(n)$ [explanation needed]
Let $S_i$ be the sum of the array upto index $i$. Then we can directly calculate the sum of any contiguous subarray $x_i, x_{i+1}, ..., x_{j}$ using the expression $S_j - S_{i-1}$. This subarray will ...
- 166
5
votes
How can a computer run an infinite loop?
You only need two transistors for that, as demonstrated by the old joke.
How do you keep a (insert ethnicity here) busy forever?
Write "Please turn over" on both sides of a sheet of paper.
It's as ...
- 219
4
votes
Average-Case Analysis of a Simple Max-Finding Algorithm
Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to ...
- 9,007
4
votes
What is the time complexity of this algorithm?
In Python, range(0,n) iterates through the values 0, 1, 2...
D.W.♦
- 152k
4
votes
Accepted
Costs of updating arrays to contain only zeroes
To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also?
The answers to both ...
- 71.7k
4
votes
Analyzing the time complexity of nested loops
Translating for-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:
$\qquad\displaystyle\begin{align*}
\#\mathrm{...
- 71.7k
4
votes
what is halting problem?
Consider the set of all possible pairs $ \langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may ...
- 9,707
4
votes
Accepted
How many times is a for loop executed?
Consider the following code snippet:
for(int i=0;i<n;i++)
The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?
This loop ...
- 6,767
3
votes
Accepted
Proving correctness of a loop that calculates the sum of array
I think your postcondition is wrong. Since index i is initialized at 0, you're actually summing from 0 to n, not from 1 to n. The postcondition, lets call it $P$, should be:
$$ j = \sum_{k=0}^{n} a[k]...
- 98
3
votes
Average-Case Analysis of a Simple Max-Finding Algorithm
The number of times that max is assigned to is known as the number of records (or left-to-right maxima) in the permutation. The following results are standard, and can be found in a paper of ...
- 274k
3
votes
Accepted
Recurrence relations when function call is made inside loop
First, those two summation are not equivalet, the reason that the $1$ is outside is because this line in your code:
int x=1,k;
Try to run this "by hand" and ...
- 449
3
votes
3
votes
Loops at low level
Underneath there are normal loops, or vectorized instructions (SIMD instructions where possible).
It is not possible to avoid loops at all - you can unwind them if you know number of iterations in ...
- 9,385
3
votes
What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)?
It's not hard to see how many times c gets incremented. Each $+$ in the table below represents one c++ operation.
$$\begin{...
- 1,012
3
votes
Proving correctness of an exponentiation routine
A standard approach to proving correctness of a program involving a loop is to use a loop invariant. Loop invariant $P(j)$ is a statement indexed by the iteration number $j$ (or a parameter related to ...
- 1,453
Only top scored, non community-wiki answers of a minimum length are eligible