# Questions tagged [loops]

The tag has no usage guidance.

146 questions
Filter by
Sorted by
Tagged with
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?...
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: ...
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: ...
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 ...
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 ...
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 ...
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 ...
24 views

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(... 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: ... 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[... 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? ... 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 ... 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? 0answers 88 views ### Runtime of this function in Theta [duplicate] ... 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 ... 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 ... 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: ... 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 ... 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 ... 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: ... 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$$)$... 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? 0answers 48 views ### Complexity of this function [duplicate] I have this function ... 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: ... 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 ... 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 ... 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 ... 0answers 17 views ### Confusion with space and time usage [duplicate] The following is my own set-up code: ... 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 ... 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++) ... 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. ... 2answers 113 views ### Approximating the runtime of a practice problem [duplicate] I'm studying for an algorithms exam and came upon the problem : ... 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 ... 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? 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 ... 1answer 63 views ### Big-O comparison different arrangements of similar code [duplicate] The following code should have a run time of$O(N)$, ... 1answer 98 views ### Why is this an infinite loop? [closed] ... 0answers 7 views ### Class inheritance hierarchy Consider the inheritance hierarchy shown below. Each part of this question is independent. ... 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, ... 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 ... 2answers 2k views ### Time Complexity of a iterative program [duplicate] ... 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) ... 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. ... 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. ...