# Questions tagged [loops]

The tag has no usage guidance.

147 questions
Filter by
Sorted by
Tagged with
2k 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 ...
60 views

### make Magic Square? [closed]

I need to write a function that takes in a 2D list, that is a NEARLY magic square, meaning that if you perform ONE swap, it becomes a magic square. The function would take in this nearly magic square, ...
2k views

### Runtime analysis of a nested loop

I have some difficulties performing the worst case analysis on this algorithm. The outermost loop is executed $2N$ times. The while loop, in the worst case, will increase by $2$ each time, so it ...
30 views

### What is an array that can be iterated circularly an infinite amount of times called?

I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.
296 views

### Find the efficiency class

I have to find the efficiency class of this algorithm b = 3 a = 4 for i = 4 to n^2 if (i mod 2 == 0) a = a+2 else b = b*3 end for I ...
780 views

### Solving complexity using summation

I have the following algorithm: func() { for(i=1; i<n; i=i*2) print("aa"); } How can I find Big-Oh using summation?
269 views

### Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
353 views

### Loop invariant: decreasing a variable and swapping it

As an example exercise, we were asked to find the loop invariant for this bit of code. ...
2k views

### Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
1k views

### Sum number of times statement is executed in triple nested loop

I have this code fragment: for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) for( k=0; k<j; k++ ) S; I need to find the number of times ...
292 views

### Can a Turing machine decide if a LOOP program stops for the integer input 0

This is a question I found in a practice exam while I am preparing for my mid term exam. The answer needs justification, either a pseudo code or a logical explanation why not. What puzzled me about ...
557 views

### Asymptotic time complexity of a two-loop program

I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for: ...
73 views

### Running time of algorithm (effect of j*j in for loops) - Theta Runtime

In Theta notation what are the running times of these algorithms? Algorithm 1 for i=1..n j=1 while j*j <= i: j = j + 1 Since the outer loop ...
28 views

118 views

### Loop termination - Loop invariant

(x >= 0 && y >= 0) q = 0; r = x; while ( r >=y ) { r = r - y; q = q + 1; } (x = q*y +r) && (r >= 0) && (r < y) For ...
716 views

### Complexity of while loop using series

For the following code fragment: i = 1; s = 1; while(s <= n) { i++; s = s+i; printf("x"); } How can we go about proving the time complexity of ...
171 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: ...
323 views

### Prove correctness of iterative LCM algorithm

I have been trying to prove the following algorithm, without success. Here is the C-Style pseudocode: ...
53 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 ...
482 views

### Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra

Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs? Long version and some background: Before ...
42 views

### Why does this code return $\frac{count}{2}$ instead of $count$?

I am reading "Algorithms 4th Edition" by Sedgewick & Wayne. The following method computes the number of self loops of an undirected graph $G$. Why does this code return $\frac{count}{2}$ instead ...
23 views

### Nested Function stuck on iteration update

I want to solve the Sparse Extended Information Filter Slam described by Dr. Sebestian Thrun in Probabilistic Robotics.I stuck in some nested function. The algorithm is described in page 309 in this ...
54 views

### What changes do I need to make to my algorithm to make this scene from a different angle? [closed]

The code below is in F#. It creates a scene which looks like a perspective coming from the top left. I thought if I would change i % j = w then it would come from ...
29 views

### Scheduling loop

I do not understand how do you write schduled loop from unscheduled one. The unscheduled loop straightforward if you follow the stall rules. The rules say you are supposed to stall after L.D but in ...
360 views

### Run Time of Nested Loop

In the following loop for i = 1 to n doSomething O(1) for j = 1 to k doSomething O(1) Is the runtime still $O(nk)$ even with the expression in ...
509 views

### How to get Loop invariants to prove program is correct in Hoare logic

start off stating the definition of a loop invariant. It is a condition that must be true at the start of the loop and must be true after each iteration of the loop. I understand what it is but i have ...
76 views

### Hoare correctness proof for a recursive definition of multiplication

Given the program: {y=y0 ^ y>=0} z=0; while (y>0){ z=z+x; (1) y=y-1; } {z=x*y0} I am having trouble finding the ...
124 views

### Maximum value of LOOP-Program turing-computable

Lets consider the class of "simple" LOOP-Programs. A LOOP-Program P is inducively defined as: $P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$ ...
40 views

### Time complexity of a nested loop [duplicate]

I need to figure out the complexity of the following loop in theta notation but I can't figure it out. Some help would be much appreciated. ...
237 views

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

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

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

Let f be the function with one argument - positive integer n ...
436 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 ...
285 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 ...
165 views

### Complexity of a nested for loop [duplicate]

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows: What value is returned by the following function? Express your ...
782 views

### Bubble sort complexity [duplicate]

So I have this code: ...
824 views

### Calculating time complexity of two interdependent nested for loops

Consider the following code segment : for (int i = 1; i <= n; i++ ) { for (int j = 1; j <= n; j = j + i ) { printf("Hi"); } } Here, the ...
519 views

275 views

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

I am trying to figure out what the big o estimate of the following for loop is. ...
531 views

### what is halting problem? [duplicate]

i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure ...
30 views

### I cannot find an invariant for the following program

I have the following: (|$y=0; x=c$|) while(x > 0){y=y+a; x=x-1;} (|$y= a*c$|) This seems like a fairly simple program and I can intuitively tell that the post ...
860 views

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

I am trying to mathematically prove that the following program is correct: ...
725 views

### Finding a Hoare logic correctness proof for a Repeat-Until loop

How can we prove a program in repeat until using Hoare Logic? I've found a rule like this: {P} S {R}, {R ^ ~B -> P}, {R ^ B -> Q} for ...
222 views

### Understanding the time-complexity of Insertion Sort

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below). ...