# Questions tagged [loops]

The tag has no usage guidance.

139 questions
Filter by
Sorted by
Tagged with
1answer
47 views

### algorithm analysis - complex dependant nested loop

First of all, I know there are many questions like this on the site. But I think this case is a bit different. Consider the following code: ...
1answer
40 views

### Dealing with test condition '=' for a while loop when determining a bound function/loop variant

The following is the definition of what a bound function for a while loop must satisfy: The bound function is an integer-valued, total function of some of the inputs, variables and global data that ...
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.
1answer
30 views

### Big O of runtime operation n-m+1 [duplicate]

I have a loop that runs n-m+1 times where m = len(list_m) n = len(list_n) for i in range(n-m+1): Is this time complexity O(n-m+1)?
1answer
263 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 ...
1answer
76 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 ...
3answers
29 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, ...
1answer
76 views

### What would be the big-o time complexity of this scenario? [duplicate]

I am wondering what the time complexity of a for loop that increments the control variable, but also multiplies it inside the loop. For example ...
0answers
23 views

### Run time analysis of inner loop [duplicate]

What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[...
4answers
573 views

1answer
70 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: ...
1answer
79 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 ...
0answers
26 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 ...
1answer
31 views

### Little bit confusing to compute time complexity of nested loop [duplicate]

1 for(i=1; i<=n; i++){ 2 for(j=1; j<=n; j*=2){ 3 a[i][j]=b[i][j-1]+1; 4 } 5 } line 1 : n+1 times lnie 2 : n/2+1 times line 3 : constant time c ...
1answer
68 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 ...
2answers
516 views

### Time complexity of euler totient function

Code for finding $\phi$(n) is ...
2answers
392 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?
1answer
386 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 ...
1answer
74 views

### Complexity of a loop

If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop? I am trying to figure out the correct answer to this ...
1answer
238 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 ...
1answer
43 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: ...
0answers
74 views

### How many operations does this algorithm require?

I have the following algorithm x = 0 S = {} k = 1 while x + a[k] < n do S = S + {k} x = x + a[k] k = k + 1 end where ...
1answer
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: ...
1answer
340 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 ...
1answer
107 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)$ ...
2answers
453 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 ...
0answers
136 views

### Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...
1answer
270 views

### How to get O(Big-oh) notation for following Code [duplicate]

What i came up with is this 1) inner loop goes to 2n and at each. step it increments n/3 times threfore 2log n times it will execute 2) outer goes to n incrementing by 1 threfore n times Hence for ...
0answers
62 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 ...
2answers
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: ...
1answer
434 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