Questions tagged [loops]
The loops tag has no usage guidance.
146
questions
0
votes
1answer
57 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
399 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
46 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:
...
0
votes
2answers
413 views
Running-time cost of Tweaked Nested Loop
I understand that the following nested for-loop:
for(i=0; i<n/2; i++)
for(j=0; j<n/2; j++)
print(j)
has the runtime complexity of
which has ...
0
votes
1answer
755 views
run time analysis of a for loop [duplicate]
I am trying to prepare for a test comping up on run-time analysis. I have been hit with a for loop that is throwing me a bit. I am hoping someone can help me.
the loop is
...
0
votes
1answer
99 views
Confusion related to calculating time complexity
I have some confusion related to calculating the time complexity of this algorithm
opt(i)
for j=i:n
a = f(i,j) + opt(j+1)
end
How is the running ...
0
votes
0answers
35 views
How to draw flowchart for if condition within nested loops?
Please find my program logic as below :
Please find my flowchart for the above program logic as below:
My superior asked me correct the flowchart. But I couldn't identify my mistakes.
Please guide ...
0
votes
0answers
24 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(...
0
votes
1answer
61 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
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
47 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?
...
0
votes
1answer
126 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 ...
0
votes
3answers
42 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
0
votes
1answer
90 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 ...
0
votes
0answers
83 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
0answers
193 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: ...
0
votes
0answers
273 views
How to calculate runtime complexity of the nested loops with variable length
Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s character. The algorithm will ...
0
votes
0answers
255 views
Looking for algorithms with nested loops with unpredictable iteration counts
I am working on a compiler optimisation routine for GPUs that optimises nested loops which has unpredictable number of iterations. To test my routine I need some real-life algorithms that include this ...
0
votes
1answer
666 views
Triple nested loop where outer and inner loop are dependent on n
I am trying to count the exact/total number of iterations these nested for-loops are executed:
...
0
votes
0answers
57 views
Behavior of an algorithm with inner loop step by 2 and outer loop decrements inner loop times [duplicate]
I designed an algorithm like this but I do not know how to perform its analysis to determine how it runs $($$O(n)$, $O(n^2)$, $O(log(n)$, $etc$$)$
...
0
votes
0answers
14 views
Big o of for loop with multiplication iteration [duplicate]
For(int i=1;i<=n;i*=2)
Statement
I'm making notes for competitive exam and made this problem. But I'm not getting solution. Is it O( log n)? If so why?
0
votes
0answers
48 views
0
votes
0answers
29 views
Time complexity of nested for loop function involving mod to filter out the execution [duplicate]
I have to find the time complexity of the following program:
...
0
votes
0answers
32 views
Frequency count of while loop [duplicate]
I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count
...
0
votes
1answer
558 views
Algorithm analysis of nested loop [duplicate]
so I have this code:
for (int i=1; i < n; i=i*5)
for (j=i; j < n; j++)
sum = i+j;
And I'm wondering, what's the time complexity of this for ...
0
votes
0answers
16 views
Runtime of this loop [duplicate]
I need some advice on how to determine the runtime of this loop :
s=0
for ( i=1 , i <= 2^m ; i=i*2 ) {
s++
}
return s
With
$C_1$ = actions ...
0
votes
0answers
17 views
0
votes
0answers
31 views
Nested Loop Complexity [duplicate]
I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj).
The lists are all sorted.
My aim is to iterate through the list and match 1 or ...
0
votes
0answers
18 views
Big o notation for the algo [duplicate]
Asked this at programmers Stack Exchange, was recommend to ask here :
What would be the big o for the algo:
for (i=0; i < n*n; i++)
for(j=0; j<i*i; j++)
...
0
votes
0answers
54 views
Time complexity of complex nested for loops [duplicate]
What are the time complexities of the following code? I posted this on the general stackexchange website, but it was suggested that I post it here.
...
0
votes
2answers
113 views
Approximating the runtime of a practice problem [duplicate]
I'm studying for an algorithms exam and came upon the problem :
...
-1
votes
1answer
98 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
...
-1
votes
1answer
180 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
votes
1answer
34 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
...
-1
votes
1answer
63 views
Big-O comparison different arrangements of similar code [duplicate]
The following code should have a run time of $O(N)$,
...
-1
votes
1answer
98 views
-1
votes
0answers
7 views
Class inheritance hierarchy
Consider the inheritance hierarchy shown below. Each part of this question is independent.
...
-1
votes
1answer
249 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, ...
-1
votes
1answer
75 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
2answers
2k views
-1
votes
1answer
180 views
What is the time complexity (big O) of this nested for-loop? [duplicate]
What is the time complexity (big O) of this nested for-loop?
I believe it's either O(n) or O(n^2)
...
-1
votes
1answer
2k views
Runtime of nested loops
What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case.
...
-2
votes
1answer
2k views
What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]
I am looking for the time complexity of the following nested loops, where the inner loop is shrinking.
...
-2
votes
1answer
650 views
Complexity Analysis for a nested loop with two methods [duplicate]
Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
-2
votes
1answer
322 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 ...
