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

...