The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [loops]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
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 ...
1
vote
1answer
26 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.
1
vote
1answer
92 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 ...
1
vote
2answers
544 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?
1
vote
1answer
266 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): ...
1
vote
1answer
332 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. ...
1
vote
1answer
1k views

Explanation of the complexity of a loop [duplicate]

I am confused on the following: In the following trivial code: ...
1
vote
1answer
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 ...
1
vote
1answer
283 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 ...
1
vote
1answer
550 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: ...
1
vote
1answer
61 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 ...
1
vote
1answer
26 views

Runtime-Analysis for single loop incremented by a factor of 3

So, I'm trying to understand how to get the run time of this loop: for(int i = 1; i < n*n*n; i*=3) {...} So, far I know: loop starts at 1 finishes when $i &...
1
vote
1answer
289 views

is a while loop always an indefinite loop?

Building on this example and others found elsewhere we have two types of loops, definite and indefinite: definite being a loop that has its number of iterations known before it is executed. E.g. a ...
1
vote
1answer
79 views

How do you solve this [1,5,9,4] pair numbers problem?

So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs ...
1
vote
1answer
1k views

Runtime analysis of while-loop analysis

s = n while (s > 4) s = s / 2 else s = s - 1 Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs. $S(n)=1 + S(n/2)$ if $n$ is even $S(n)=...
1
vote
1answer
86 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 ...
1
vote
2answers
599 views

Time complexity of euler totient function

Code for finding $\phi$(n) is ...
1
vote
1answer
493 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 ...
1
vote
2answers
170 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: ...
1
vote
2answers
297 views

Prove correctness of iterative LCM algorithm

I have been trying to prove the following algorithm, without success. Here is the C-Style pseudocode: ...
1
vote
1answer
51 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 ...
1
vote
1answer
451 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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
28 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 ...
1
vote
1answer
289 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 ...
1
vote
1answer
376 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 ...
1
vote
0answers
64 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 ...
1
vote
1answer
109 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)$ ...
1
vote
0answers
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. ...
1
vote
1answer
235 views

Calculate the complexity of an algorithm [duplicate]

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

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

Let f be the function with one argument - positive integer n ...
1
vote
0answers
426 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 ...
1
vote
0answers
283 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 ...
1
vote
0answers
141 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 ...
1
vote
1answer
777 views

Bubble sort complexity [duplicate]

So I have this code: ...
0
votes
3answers
787 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 ...
0
votes
2answers
507 views

A puzzle related to nested loops

For a given input $N$, how many times does the enclosed statement executes? for $i$ in $1\ldots N$ loop $\quad$for $j$ in $1\ldots i$ loop $\quad$$\quad$for $k$ in $i\ldots j$ loop $\quad$$...
0
votes
4answers
652 views

What is the time complexity of this algorithm?

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed: She represented the cost of the algorithm by the following sum: $\sum\...
0
votes
2answers
262 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. ...
0
votes
2answers
480 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 ...
0
votes
1answer
668 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 ...
0
votes
1answer
203 views

Understanding the time-complexity of Insertion Sort

From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below). ...
0
votes
1answer
115 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....
0
votes
1answer
769 views

Proving correctness of a loop that calculates the sum of array

I am trying to mathematically prove that the following program is correct: ...
0
votes
3answers
30 views

Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers. A modular approach would be to write one function for each, thus iterating over the array thrice. However, ...
0
votes
1answer
54 views

Time complexity dependent on magnitude of input [duplicate]

I'm trying to analyze an algorithm that looks like this: def foo(L): for n in L: for x in range(n): ... What would be its time complexity?...
0
votes
1answer
373 views

Big-O notation for nested loops that might skip iterations

When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately? Hypothetical example: ...
0
votes
1answer
44 views

Loop Transforms to Increase Parallelism

I have the need to parallelize as much as I can (in order to make it run fast) the following part of an algorithm: ...