Questions tagged [loops]
The loops tag has no usage guidance.
141
questions
0
votes
0answers
21 views
Using induction vs invariants to prove correctness of algorithms
In my algorithms class I have generally been proving algorithms by induction. So for example, given some algorithm $A(n)$ that computes $x$, I show that the algorithm works for some base case, say $A(...
1
vote
1answer
59 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
25 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
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
3answers
84 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 ...
1
vote
1answer
287 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 ...
0
votes
1answer
54 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:
...
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, ...
-1
votes
1answer
92 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
...
0
votes
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[...
0
votes
1answer
45 views
What will be big O complexity for this loop? [duplicate]
I am not able to understand time complexity of this for loop.
While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?
...
2
votes
2answers
50 views
Quotient in LOOP program [closed]
I want to construct a LOOP-computable program for the integer division (quotient):
x = a DIV b
The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)
I ...
0
votes
1answer
53 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?...
1
vote
1answer
82 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 ...
0
votes
1answer
367 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:
...
-1
votes
1answer
195 views
Finding time complexity when while loop included [duplicate]
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, ...
6
votes
5answers
3k views
How can a computer run an infinite loop?
I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop ...
-1
votes
1answer
74 views
Measuring infinite loops [closed]
Theoretically, is there a way to measure how many infinite loops are running at a given point in time? In other words, is there a way to freeze everything and get a number on how many infinite lines ...
-1
votes
1answer
178 views
What is the procedure to find the time complexity of python program? [duplicate]
Is there any kind of function which is used in python to calculate the time complexity of another function?
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
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 ...
0
votes
1answer
117 views
Exponential nested Loop Big O complexity calculation [duplicate]
Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with 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 ...
5
votes
0answers
212 views
How Janus (Reversible Programming Language) `if`, `while`, and Update Work
In Reversible Computing, all program statements are reversible. I understand for example that the following:
\begin{align}
x\ {+}&{=}\ 4\\
y\ {*}&{=}\ x\\
x\ {-}&{=}\ 10
\end{align}
Has ...
2
votes
1answer
278 views
Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?
Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case?
Even in the case of a reversely sorted list, it's not like it'll have ...
0
votes
3answers
41 views
What is the most used way to write for-loop as pseudocode?
for $e\leftarrow1$ to 8 do
for $e\in[1,8]$ do
for $e\in\{x\in\mathbb{N}|1\le x\le8\}$ do
What is more preferred?
0
votes
0answers
88 views
1
vote
1answer
991 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)=...
2
votes
1answer
81 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:
...
1
vote
1answer
85 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
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
votes
1answer
33 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
...
3
votes
1answer
76 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 ...
1
vote
2answers
593 views
1
vote
2answers
528 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
478 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 ...
0
votes
1answer
81 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 ...
1
vote
1answer
283 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 ...
0
votes
0answers
76 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 ...
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:
...
2
votes
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:
...
1
vote
1answer
1k views
Find Number of even subarrays $O(n)$ [explanation needed]
So I found a solution to this problem here http://marcodiiga.github.io/number-of-even-sum-subarrays but I am unsure of exactly how it works. I get the premise that in order to have an even sum it must ...
1
vote
1answer
375 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 ...
0
votes
2answers
478 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
0answers
166 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: ...
-2
votes
1answer
299 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 ...
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)$ ...
2
votes
1answer
546 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
-1
votes
2answers
2k views
