# Questions tagged [loops]

The tag has no usage guidance.

146 questions
Filter by
Sorted by
Tagged with
1k views

### Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
11k views

### Why are loops faster than recursion?

In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But ...
326 views

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

I'm working on my own little programming language for educational purposes, and I've run into a little bit of a problem. There are a few different solutions for it, but all of them seem inelegant - ...
715 views

### Loop variant for a while loop that occasionally doesn't decrease?

I'm working on practice problems for a test I have, and every example of loop variant decreased with every iteration of the loop. On this one, the values remain the same when a < b. My attempts ...
3k views

### How can a computer run an infinite loop?

I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop ...
16k views

### What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
944 views

### Looping and branching with Algorithmic Differentiation

Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...
1k views

### Loops at low level

When programming with high level languages like Python or Matlab, it is always better to model the problem such as the solution is some kind of vector or matrix multiplication, to avoid loops. But ...
482 views

### From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
222 views

### How Janus (Reversible Programming Language) if, while, and Update Work

In Reversible Computing, all program statements are reversible. I understand for example that the following: \begin{align} x\ {+}&{=}\ 4\\ y\ {*}&{=}\ x\\ x\ {-}&{=}\ 10 \end{align} Has ...
10k views

### Triple nested for-loops [duplicate]

Possible Duplicate: A puzzle related to nested loops I am trying to count the exact/total number of iterations the following nested for-loops are executed: ...
9k views

### Time complexity formula of nested loops

I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides. ...
1k views

### Analyzing programs with multiple for-loops

If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these... the ones like <...
1k views

### Recurrence relations when function call is made inside loop

int fun (int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n – k); return x; } What is the value of fun(5)? I ...
85 views

### time complexity when power is involved in iteration

How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * <something>. I ...
134 views

### Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
693 views

### Running time function for an algorithm with while and for loop

I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and ...
822 views

### Theta Runtime of Nested for Loops

I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much <...
37 views

### Print to video permutations

You want to print vectors with n elements, where: the first element can have the values: e1.1, e1.2, e1.2; the second element can assume the values: e2.1, e2.2, e2.3; ...; ...; the nth element can ...
92 views

### Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation: ...
590 views

### Do recursive algorithms generally perform better than their for-loop counterpart?

I'm sure this is not a challenge for you but it remains an open question for me: Is it wise to prefer a recursive algorithm over its for-loop counterpart? E.g. take the evaluation of the natural ...
134 views

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

I have an algorithm similar to this: i=1 while(i < n) { //something in O(1) while(i < n && cond) { //something in O(1) i++ } i++ } ...
3k views

### Time complexity of a triple nested loop with squared indices

I have seen this function in past year exam paper. ...
60 views

### 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? And in that case, ...
41 views

### Does any algorithm loops at some point?

Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point? If ...
669 views

### Analyzing the time complexity of nested loops

So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so. What is the time complexity of this code? ...
55 views

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

I am wondering, if in the LOOP programing language, whether instances of the LOOP x DO P END are defined to stop in the case $x < 0$. The definition only says "...
458 views

### Proving correctness of an exponentiation routine

I have the following exponentiation routine, which takes $O(\log n)$ steps ...
69 views

### Quotient in LOOP program [closed]

I want to construct a LOOP-computable program for the integer division (quotient): x = a DIV b The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language) I ...
100 views

### Big Oh notation for a function with two inputs of linear growth

I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function: ...
2k views

### Recursion call inside a for loop time

I'm analyzing a piece of code that has a recursive call inside a for loop such as: ...
643 views

### What is more effective, a do while or a while?

I mean, with the same code, if I modify a do while into a while in this way: do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change in the code? B = condition S; = instructions
297 views

### Can a vectorized computation always be parallelized?

If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, ...
293 views

### Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case? Even in the case of a reversely sorted list, it's not like it'll have ...
1k views

### How can I convert a for loop to a recursive function?

My loop is pretty simple. The function takes in two parameters, a and b; both are integers where a<=b. The function will then create a list of numbers from a to b. This is what I created: ...
394 views

### Big O complexity of algorithm with a nested for loop only running once

I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^...
469 views

### Calculate Complexity, loop incremented by log(k)

I'm preparing for an exam, and I ran across the following algorithm: ...
524 views

### Simplifying a nested sum

I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big $O$...
301 views

### When are range-based for loops better than regular for loops? [closed]

Is it when you need faster performance, to iterate over a container, or when you don't need an index variable? From my understanding it should be when you need to iterate over a container. Am I ...
393 views

### Time complexity of nested loops help [duplicate]

How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone ...
601 views

### What is the difference between a loop and a natural loop?

Is there a difference between a loop and a natural loop? Natural loops are defined as having a back edge to a head block that dominates it. If you have a natural loop nested inside of another ...
45 views

### A linear code, what is that?

I have been trying to understand the polytope model used for loop nest optimizations. Now while going through some of the thesis written on this, i came across the term/phrase "linear code" a number ...
20 views

### What would be the time complexity if a recursive function is inside a loop? [duplicate]

I am confused in calculating the time complexity for a recursive function inside a loop. ...
830 views

### How can I use nested loops to print out this triangle word pattern? [closed]

I'm trying to make a pattern that looks like this: And am given this code to start: ...
650 views

### Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
1k views

### Find Number of even subarrays $O(n)$ [explanation needed]

So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must ...
383 views

### Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-...
444 views

### provability of while loop vs for loop [closed]

I'm abit afraid to ask this question here seeing as I asked it on programmers SE already, the thing is I think the question is more about the underlying theory than the use in practice (or call it ...
An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic ...