Hot answers tagged

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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 1,000
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 ...
user avatar
11 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 ...
user avatar
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-...
user avatar
9 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 ...
user avatar
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 ...
user avatar
6 votes
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: ...
user avatar
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-...
user avatar
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 ...
user avatar
  • 320
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 ...
user avatar
  • 29.1k
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. ...
user avatar
  • 141k
5 votes

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, ...
user avatar
5 votes
Accepted

How to bridge theory and implementation for while loops?

So I managed to solve this issue today. The code for my while loop: ...
user avatar
  • 499
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 ...
user avatar
  • 19.1k
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 ...
user avatar
  • 19.1k
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 ...
user avatar
  • 141k
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 ...
user avatar
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 ...
user avatar
  • 219
4 votes

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 ...
user avatar
4 votes

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 ... ...
user avatar
  • 25.2k
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 ...
user avatar
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 ...
user avatar
  • 70.9k
4 votes

What is the time complexity of this algorithm?

In Python, range(0,n) iterates through the values 0, 1, 2...
user avatar
  • 141k
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{...
user avatar
  • 70.9k
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 ...
user avatar
  • 9,612
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 ...
user avatar
  • 5,164
3 votes

Loops at low level

Consider the following simple python3 script: ...
user avatar
3 votes

What is the Big O estimate of a nested for loop?

The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky ...
user avatar
  • 29.1k

Only top scored, non community-wiki answers of a minimum length are eligible