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

### Why are loops faster than recursion?

The reason that loops are faster than recursion is easy. A loop looks like this in assembly. ...

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

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

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

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

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

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

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

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

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

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

### What is the time complexity of this algorithm?

In Python, range(0,n) iterates through the values 0, 1, 2...