# Questions tagged [loops]

The tag has no usage guidance.

140 questions
1k views

### Nested Loop Time Complexity vs Successive Loops

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 ...
114 views

### Construct a loop program for equality

I want to construct a loop-computable program for this construction: IF x1 = c THEN P ELSE P' I know how to transform if else construction in loop , but I can't understand how to check the equality....
500 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: ...
216 views

### Calculate the complexity of an algorithm [duplicate]

I have an algorithm here and it wants me to calculate the complexity: ...
254 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 ...
262 views

### How to calculate runtime complexity of the nested loops with variable length

Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s character. The algorithm will ...
169 views

### Complexity of the algorithm to find occurences of a given number in a given array

I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm: ...
342 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 ...
59 views

### Big-Oh of algorithm

I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345. The algorithm looks like: ...
716 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 ...
28 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 ...
36 views

### Time complexity ( $\Theta$ ) of function [duplicate]

Let f be the function with one argument - positive integer n ...
293 views

### Prove correctness of iterative LCM algorithm

I have been trying to prove the following algorithm, without success. Here is the C-Style pseudocode: ...
214 views

### Looking for algorithms with nested loops with unpredictable iteration counts

I am working on a compiler optimisation routine for GPUs that optimises nested loops which has unpredictable number of iterations. To test my routine I need some real-life algorithms that include this ...
368 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^...
404 views

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

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

### Triple nested loop where outer and inner loop are dependent on n

I am trying to count the exact/total number of iterations these nested for-loops are executed: ...
111 views

### Approximating the runtime of a practice problem [duplicate]

I'm studying for an algorithms exam and came upon the problem : ...
556 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 ...
63 views

### Big-O comparison different arrangements of similar code [duplicate]

The following code should have a run time of $O(N)$, ...
57 views

### Behavior of an algorithm with inner loop step by 2 and outer loop decrements inner loop times [duplicate]

I designed an algorithm like this but I do not know how to perform its analysis to determine how it runs $($$O(n), O(n^2), O(log(n), etc$$)$ ...
556 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? ...
383 views

### Bridge Crossing Problem Proof?

I'm trying to find an optimal solution that will work for the bridge crossing problem. In case you don't know it you can check out the Ted Ed video on it. They show how you can do it with 5 people but ...
14 views

### Big o of for loop with multiplication iteration [duplicate]

For(int i=1;i<=n;i*=2) Statement I'm making notes for competitive exam and made this problem. But I'm not getting solution. Is it O( log n)? If so why?
48 views

### Complexity of this function [duplicate]

I have this function ...
107 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 ...
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 "...
383 views

### Proving correctness of an exponentiation routine

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

### Time complexity of nested for loop function involving mod to filter out the execution [duplicate]

I have to find the time complexity of the following program: ...
1k views

### What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
266 views

### How to determine big O of a variable loop

I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the ...
9k 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 ...
508 views

539 views

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

Given this piece of code: ...
32 views

### Frequency count of while loop [duplicate]

I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count ...
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: ...
50 views

### Runtime of algorithem when the internal for depend on the external for

I'm trying to find the running time of this pseodocose: int x=0,i,j for (i=1;i<=n;i++) for(j=1;j<=n+r;j=j+i) x=x+j; What I did: First I checked ...
379 views

### Running-time cost of Tweaked Nested Loop

I understand that the following nested for-loop: for(i=0; i<n/2; i++) for(j=0; j<n/2; j++) print(j) has the runtime complexity of which has ...
704 views

### Proving correctness of a loop that calculates the sum of array

I am trying to mathematically prove that the following program is correct: ...
449 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 ...
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 ...
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. ...
277 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, ...
747 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: ...
608 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 ...
95 views

...
606 views

### run time analysis of a for loop [duplicate]

I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me. the loop is ...
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 ...