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 ...
Klorax's 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 ...
ratchet freak's 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. ...
Johan's user avatar
  • 1,060
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 ...
Derek Elkins left SE's user avatar
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 ...
Markus Mottl's user avatar
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 ...
Yuval Filmus's 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 ...
hobbs's user avatar
  • 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 ...
Joey Eremondi's user avatar
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.'s user avatar
  • 158k
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 ...
Andreas G.'s 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 ...
Graham's user avatar
  • 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 ...
templatetypedef's user avatar
4 votes

What is the time complexity of this algorithm?

In Python, range(0,n) iterates through the values 0, 1, 2...
D.W.'s user avatar
  • 158k
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 ...
Raphael's user avatar
  • 72.3k
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{...
Raphael's user avatar
  • 72.3k
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 ...
fade2black's user avatar
  • 9,817
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 ...
Caleb Stanford's user avatar
3 votes
Accepted

Nested Loop Time Complexity vs Successive Loops

I think that the first algorithms running time is actually $\mathcal{O}(x^4)$. The outer for loop executes exactly $x$ times, the inner for loop executes at most $x$ times during every one of these $...
swingballchamp42's user avatar
3 votes
Accepted

Can LOOP-Programm stop when its value goes below 0?

Variables in LOOP programs are non-negative, so the problem never arises; the instruction $x_1 = x_1 - c$ assigns $x_1$ the value of $\max(x_1-c,0)$. Note that the instruction $x_1 = x_1 - x_2$ isn't ...
Yuval Filmus's user avatar
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 ...
Denis Pankratov's user avatar
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{...
200_success's user avatar
  • 1,012
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 ...
Yuval Filmus's user avatar
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]...
Alf's user avatar
  • 98
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 ...
3SAT's user avatar
  • 449
3 votes

Dealing with test condition '=' for a while loop when determining a bound function/loop variant

$n-j+1$ should work as it satisfied the three properties of a bound function. It is definitely an integer valued function as all variables and 1 are integers. Since $j$ is increased by 1 in every ...
Potato's user avatar
  • 131
3 votes
Accepted

I cannot find an invariant for the following program

Figure out what the value of y is, depending on x, a, and c. Prove that your formula is correct before the first iteration, and prove that if it is true before an iteration then it is also true after ...
gnasher729's user avatar
  • 29.4k
3 votes
Accepted

Does any algorithm loops at some point?

You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state. However, I would like to warn against interpreting this ...
Andrej Bauer's user avatar
  • 30.3k
3 votes
Accepted

Do there exist coding languages where the halting problem is solvable but not trivial

I think I understand what you are trying to ask. But you may have to work harder on the asking to get a non-trivial answer. As it stands, your question has a trivial answer. Take a language that ...
babou's user avatar
  • 19.4k
3 votes
Accepted

How to calcualte the Big-O complexity of the following algorithm?

for(i=1;i<=n;i++) { for(j=1 ; j <= i*i ; j++) { for(k=1 ; k<= n/2 ; k++) { x = y + z; } } } The triple-...
BearAqua in Agua's user avatar

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