Questions tagged [loops]
loops with relevance to computer programming are a sequence of instructions that is continually repeated until a certain condition is reached or a condition wasn't met.
196 questions
1
vote
3
answers
242
views
When do we multiply or add the time complexities of loops?
I am confused about calculating the time complexity of the following function.
...
- 13
2
votes
1
answer
72
views
"Consecutive statements" in Static control Part(SCoP)
Context:
I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.
Paper ...
- 123
2
votes
0
answers
119
views
SCoP, Iteration Domain in Polyhedral Optimization and use of Presburger arithmetic
Context:
While exploring the fundamentals of polyhedral optimization and attempting to explore a connection from the input Static Control Part (SCoP) to the iteration domain from birds eye view, I am ...
- 123
1
vote
1
answer
96
views
Loop Bounds vs. Iteration Domain in Polyhedral optimization
Context:
I was reading a tutorial on polyhedral optimization. But got confused while trying to translate the iteration domain (i.e. loop bound) to set builder notation.
Problem Description:
A code ...
- 123
0
votes
0
answers
13
views
Hyperplanes and loop parallelization
Is it possible for the hyperplane method for loop parallelization, to return more than one hyperplanes whose points are scheduled to be executed at the same time? In an example I studied (Shang & ...
1
vote
1
answer
43
views
Iteration scheduling vs processor scheduling
In parallel programming the iteration scheduling is defined as the determination of the logical execution time for each loop iteration, while in operating systems, the processor scheduling (FCFS etc) ...
0
votes
0
answers
15
views
Dependency testing and parallel compilers
I currently study well known dependency testing for automatic loop parallization from parallel compilers (ZIV, SIV, MIV, Single Variable Constraint, Multiple Variable Constraint, Acyclic Test, Fourier ...
-1
votes
4
answers
196
views
Can code "run forever" if it contains no loops?
Is it possible to write a piece of code that will run forever without using a loop?
- 115
0
votes
1
answer
57
views
Can a trie or DAWG loop?
I am looking at DAWGs, which are compressed tries, like this:
It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure.
For example, I am ...
- 2,295
1
vote
1
answer
57
views
Big O analysis of a sorting algorithm that counts smaller elements
How do I prove the runtime of an algorithm with Big O notation? I don't know much about O notation, I just I know how to compare sets of functions with each other and I'm also familiar with the master ...
- 13
1
vote
1
answer
124
views
Time complexity for finding the number of triangles in a graph
In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using ...
- 195
4
votes
1
answer
188
views
Tail call optimization via translating to CPS
I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function
...
- 235
1
vote
2
answers
81
views
Can a strict right fold be implemented in a single loop?
A strict left fold is straightforward to implement as a loop, rather than with recursion:
...
- 413
0
votes
1
answer
38
views
how can I fix my SQL for loop so that the index is not out of bounds?
I want to create a table that has the following results:
...
- 103
-2
votes
1
answer
64
views
What does this condition in the for loop mean?
I found a solution of exercise C-8.28 from Data Structures and Algorithms in Java (6th Edition), but I'm having trouble understanding how the for loop condition works here.
...
- 225
2
votes
1
answer
168
views
What loop invariant can be used for this loop? (Algorithm to check if a sequence is stack permutable)
I've written a function that gets a permutation and checks if that permutation can be reached using a stack from an input sequence which is <1,2,3,...,n>. (we take elements from left)
For ...
- 164
2
votes
3
answers
2k
views
Determining Big O of a for loop nested within a while loop
I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :)
Im a ...
- 23
0
votes
1
answer
93
views
Proving loop invariant for a possibly nonterminating while loop
I started studying through Aho, Ullman - Foundations of Computer Science as a free time exercise. In the second chapter about loop invariants and inductive proofs, there is a starred exercise.
...
- 293
0
votes
0
answers
71
views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
- 125
3
votes
3
answers
84
views
Explicit form of Hofstadters bluediag in floop
In " Gödel, Escher, Bach" Hofstadter introduces the programming languages Bloop and Floop. Relevant here is mostly that Floop is Turing complete, while Bloop differs from Floop in one aspect:...
- 761
0
votes
1
answer
73
views
Time complexity when loop index is an exponent
For any $n$ and any $x$, if one implements a loop to calculate:
$$\sum_{i=0}^n x^i$$
What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$?
What confuses me is the ...
- 1
-1
votes
2
answers
51
views
why Loop-Programm always terminates
well-known that a loop-programm in Theoretical computer science always terminates, but why do that java example not?
for( ; ; ){ }
-4
votes
1
answer
783
views
Why can't I break out of this do while loop in java?
Even though the input I type is a "Y" or "N" string, I can't break out if this while loop. Can anyone tell me why?
...
1
vote
1
answer
34
views
Rigorously show that this program outputs $2n-$ #number of ones in binary representation of $n$ stars
Given following program:
while n > 0 do
for i = 1 to n do
print '*'
n = n / 2
where $/$ is integer division as usual. We want to calculate ...
- 575
1
vote
2
answers
335
views
Loop Invariants: Can someone explain this concept?
I am reading Algorithms Unlocked By Tom Cormen and find this concept a little confusing.
Why is it that we require loop invariants and how does it help in analyzing algorithms?
- 139
1
vote
1
answer
27
views
Possibility of using loops instead of traps
Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is
Here I used q3 as a trap.
But could I do this instead?
I have not used trap in the 2nd ...
- 167
1
vote
2
answers
277
views
Why is there no "traditional"-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?
Why is there no algebraic definition of algorithm besides recursive functions?
If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link?
...
- 548
0
votes
1
answer
1k
views
In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?
I'm playing around with C++ and was looking at how to loop through an array of unknown length. The following code was suggested and works perfectly from the little testing I've done:
...
0
votes
0
answers
27
views
What are advantages of "streaming" syntax in functional languages with for-yielding like Scala?
In Scala we can print list
val nums = (1 to 10).toList
with both
...
- 117
1
vote
0
answers
17
views
While-Programm Composition & Example
I've just learned While-Programms. In case you're not familiar with it, a W-P is inductively defined as...
$x_i \leftarrow x_j+c$ (Addition for every $i,j \in \mathbb{N}$)
$x_i \leftarrow x_j-c$ (...
- 167
1
vote
0
answers
141
views
Sub-matrix with minimum size of $k$ and minimum sum
We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
- 111
0
votes
0
answers
42
views
How many times whille loop will be executed when we double the value?
Consider this loop:
for i = 1 to n
j = i
while j < n
j = j + j
end while
end for
How many times the while loop will ...
- 35
-1
votes
1
answer
74
views
Condition in the Dependent Loops
I'm stuck with nested for loops that are dependent on the previous loop:
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
x = x+1
the part that is confusing ...
1
vote
0
answers
30
views
Correct terminology for $P1;P2$?
This question is about the correct terminology. Let $P1$ and $P2$ be two LOOP programs. Then $P1;P2$ is also a LOOP program, which executes $P1$ and then executes $P2$. Would this be called ...
- 463
2
votes
0
answers
51
views
Understanding the simulate of an IF loop program through a LOOP program
We have the following operation $\text{IF} \ x_i =0 \ \text{THEN} \ P \ \text{END}$. I want to simulate this using a $\text{LOOP}$ program. Here is what I have:
$$\text{IF} \ x_i = 0 \ \text{THEN} \ P ...
- 463
0
votes
0
answers
49
views
Calculate all pairs of outer products between columns in matrix
Imagine you have a matrix m of dimension MxN
What I'm trying to do is get a set of elements (of length N*(N-1)/2) of the diagonal elements (each of whose individual length would be M) of the outer ...
- 1
0
votes
1
answer
137
views
How can I find this code block's execution time t(n) and big O notation?
Hello I am a CSE student and this question was in my homework.
...
user128778
1
vote
1
answer
171
views
What is loop invariant for this loop?
As far as i understand all loops have a loop invariants. My understanding is that loop invariant is an argument that is true at the beginning of the loop block as well as at the end of the loop.
For ...
-2
votes
1
answer
183
views
"what does the 1 to 10 mean?" FOR number ← 1 TO 10
"what does the to 10 mean?" FOR number ← 1 TO 10
0
votes
1
answer
221
views
How to calcualte the Big-O complexity of the following algorithm?
I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3).
<...
- 113
0
votes
1
answer
186
views
understanding loop invariants
I have a bit of experience with loop invariants but I'm not really clear on them. I'm trying to learn them through an Algorithm I have.
...
1
vote
0
answers
51
views
Complexity Values for Specific Code/Functions
(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
- 11
1
vote
1
answer
2k
views
Arbitrary depth nested for-loops without recursion
Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.
...
- 143
3
votes
2
answers
344
views
Do there exist coding languages where the halting problem is solvable but not trivial
Does there exist a coding language where
1. It is always possible to determine whether a computer program will halt or run forever. And
2. The answer is not always yes. (or always no)
So languages ...
- 366
0
votes
1
answer
150
views
Calculate the number of iterations in unusual nested loop
I am trying to calculate the number of iterations of a sequence of nested loops of the form:
\begin{equation}
N = \sum_{j=0}^{j_T} \sum_{k=0}^{j} \sum_{l=0}^{k} \sum_{n=n_0}^{n_T} 1
\end{equation}
...
-2
votes
1
answer
65
views
What is the time complexity of the following triple nested loop? Kindly solve in term of n
I want to ask that what is the time complexity of this function (triple nested loop)
.Kindly analysis completely so that I can understand.
...
0
votes
2
answers
209
views
What is a loop variable?
In the context of compilers, what exactly is a loop variable (if there is a standard definition)?
Every read/write make up for the loop variable, or only writes make them up? Or is it writes in the ...
-1
votes
1
answer
396
views
Asymptotic Analysis of Nested Loops with Conditionals
I'm trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows:
<...
- 1
1
vote
1
answer
104
views
Difficulty in understanding this summations to analyze time complexity
I wanna know if what this link https://stackabuse.com/shell-sort-in-java/'s calculation of the complexity of shell sort is true.
Here's the shell sort algorithm:
...
- 13
1
vote
2
answers
13k
views
How many times is a for loop executed?
Consider the following code snippet:
for(int i=0;i<n;i++)
The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?
According to what ...
- 35