# Tag Info

### 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
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,108
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,000

### 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.8k
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 ...
• 226

### 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-...
• 80.2k
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 ...
• 270k

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

### Nested loops: Still $\mathcal O(n)$?

What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like: ...
• 309

### 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-...
• 270k

### 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 ...
• 320
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.1k

### 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. ...
• 141k

### How to bridge theory and implementation for while loops?

I think you're missing the notion of continuation. Although your compiler may not rely on that notion, as a compiler designer with a functional language as source or intermediate (or target) language, ...
Accepted

### How to bridge theory and implementation for while loops?

So I managed to solve this issue today. The code for my while loop: ...
• 499

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

### 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 ...
• 141k
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

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

### Finding a Hoare logic correctness proof for a Repeat-Until loop

Note that the loop is not the outermost construct in your program; that is a sequential composition. In order to apply this rule, you first need to take care of the initial assignments. In this case ...
• 2,148

### Calculating time complexity of two interdependent nested for loops

Since you are only interested in the time complexity and can ignore a constant factor of two: Replace 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ... ...
• 25.2k

### 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 ...
• 8,857
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 ...
• 70.9k