All Questions
Tagged with algorithm-analysis loops
82
questions
0
votes
1answer
31 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)?
0
votes
1answer
51 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:
...
-1
votes
1answer
83 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
1answer
43 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
51 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
59 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
337 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
169 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, ...
0
votes
1answer
107 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 ...
2
votes
1answer
267 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
0answers
88 views
1
vote
1answer
916 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
76 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
votes
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
...
3
votes
1answer
71 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
543 views
1
vote
2answers
461 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
439 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
78 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
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 ...
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:
...
0
votes
0answers
146 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
283 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
votes
2answers
2k views
1
vote
0answers
40 views
Time complexity of a nested loop [duplicate]
I need to figure out the complexity of the following loop in theta notation but I can't figure it out. Some help would be much appreciated.
...
1
vote
3answers
1k views
Nested Loop Time Complexity vs Successive Loops
An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic ...
1
vote
1answer
225 views
Calculate the complexity of an algorithm [duplicate]
I have an algorithm here and it wants me to calculate the complexity:
...
0
votes
0answers
265 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 ...
1
vote
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:
...
2
votes
1answer
376 views
Time complexity of nested loops help [duplicate]
How exaclty do you determine this specific codes runtime is theta(n^2)??I can see theres two while loops which go from i and j to n but would like a more precise way of determing this? If someone ...
1
vote
0answers
59 views
Big-Oh of algorithm
I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345.
The algorithm looks like:
...
6
votes
2answers
817 views
Looping and branching with Algorithmic Differentiation
Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...
1
vote
0answers
36 views
Time complexity ( $\Theta$ ) of function [duplicate]
Let f be the function with one argument - positive integer n
...
1
vote
2answers
294 views
Prove correctness of iterative LCM algorithm
I have been trying to prove the following algorithm, without success.
Here is the C-Style pseudocode:
...
2
votes
1answer
375 views
Big O complexity of algorithm with a nested for loop only running once
I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^...
2
votes
1answer
437 views
Calculate Complexity, loop incremented by log(k)
I'm preparing for an exam, and I ran across the following algorithm:
...
0
votes
1answer
608 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
2answers
112 views
Approximating the runtime of a practice problem [duplicate]
I'm studying for an algorithms exam and came upon the problem :
...
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$$)$
...
2
votes
3answers
607 views
Analyzing the time complexity of nested loops
So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.
What is the time complexity of this code?
...
1
vote
0answers
413 views
Bridge Crossing Problem Proof?
I'm trying to find an optimal solution that will work for the bridge crossing problem. In case you don't know it you can check out the Ted Ed video on it. They show how you can do it with 5 people but ...
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
3
votes
1answer
125 views
Amortised analysis of a simple loop and 3 operations
I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.
Operation OP(S,X[i]) has complexity ...
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:
...
-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.
...
0
votes
4answers
611 views
What is the time complexity of this algorithm?
In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:
She represented the cost of the algorithm by the following sum:
$\sum\...
2
votes
1answer
60 views
Costs of updating arrays to contain only zeroes
To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also?
And in that case, ...
1
vote
2answers
601 views
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
...
