Skip to main content
Share Your Experience: Take the 2024 Developer Survey

All Questions

Filter by
Sorted by
Tagged with
1 vote
1 answer
54 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 ...
Tomas82's user avatar
  • 13
-1 votes
1 answer
70 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 ...
Brishti Basu's user avatar
0 votes
1 answer
208 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). <...
Ravish Jha's user avatar
-1 votes
1 answer
380 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: <...
bpryan's user avatar
  • 1
0 votes
1 answer
200 views

Time Complexity of the below code? [duplicate]

here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part. What is the time complexity ...
teddcp's user avatar
  • 159
0 votes
3 answers
344 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: ...
candh's user avatar
  • 109
-1 votes
1 answer
129 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 ...
Mr. Ice's user avatar
0 votes
1 answer
51 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? ...
manismku's user avatar
  • 103
0 votes
1 answer
448 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?...
Gaslight Deceive Subvert's user avatar
1 vote
1 answer
4k 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 ...
NANA's user avatar
  • 119
0 votes
1 answer
781 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: ...
tau's user avatar
  • 135
-1 votes
1 answer
493 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, ...
Encipher's user avatar
  • 167
0 votes
1 answer
284 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 ...
Rares Andrei's user avatar
2 votes
1 answer
828 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 ...
Magnetic Kode's user avatar
0 votes
0 answers
88 views

Runtime of this function in Theta [duplicate]

...
Brian's user avatar
  • 11
1 vote
1 answer
3k 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)=...
user avatar
2 votes
1 answer
895 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: ...
Blink's user avatar
  • 23
-1 votes
1 answer
41 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 ...
molamola's user avatar
  • 353
3 votes
1 answer
249 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 ...
salyela's user avatar
  • 133
2 votes
2 answers
3k views

Time complexity of euler totient function

Code for finding $\phi$(n) is ...
Zephyr's user avatar
  • 993
1 vote
2 answers
3k 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?
J. Doe's user avatar
  • 51
1 vote
1 answer
2k 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 ...
bigfocalchord's user avatar
0 votes
1 answer
170 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 ...
DobromirM's user avatar
  • 103
0 votes
0 answers
115 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 ...
zdm87's user avatar
  • 68
2 votes
1 answer
6k 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: ...
user83935's user avatar
0 votes
0 answers
304 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: ...
qvian's user avatar
  • 56
-2 votes
1 answer
694 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 ...
JobLess's user avatar
-1 votes
2 answers
3k views

Time Complexity of a iterative program [duplicate]

...
Manu Thakur's user avatar
1 vote
0 answers
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. ...
DariusTheGreat's user avatar
1 vote
3 answers
3k 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 ...
Jeff's user avatar
  • 113
1 vote
1 answer
247 views

Calculate the complexity of an algorithm [duplicate]

I have an algorithm here and it wants me to calculate the complexity: ...
Georgio3's user avatar
0 votes
0 answers
328 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 ...
Max Koretskyi's user avatar
1 vote
2 answers
181 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: ...
Bora's user avatar
  • 119
2 votes
1 answer
417 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 ...
78lee's user avatar
  • 79
1 vote
0 answers
66 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: ...
FreeStyle4's user avatar
8 votes
3 answers
3k 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 ...
iago-lito's user avatar
  • 195
1 vote
0 answers
37 views

Time complexity ( $\Theta$ ) of function [duplicate]

Let f be the function with one argument - positive integer n ...
glion14's user avatar
  • 11
1 vote
2 answers
880 views

Prove correctness of iterative LCM algorithm

I have been trying to prove the following algorithm, without success. Here is the C-Style pseudocode: ...
Dr C's user avatar
  • 141
2 votes
1 answer
630 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^...
Chuque's user avatar
  • 121
2 votes
1 answer
656 views

Calculate Complexity, loop incremented by log(k)

I'm preparing for an exam, and I ran across the following algorithm: ...
user60047's user avatar
0 votes
1 answer
1k 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: ...
collegesista's user avatar
0 votes
2 answers
135 views

Approximating the runtime of a practice problem [duplicate]

I'm studying for an algorithms exam and came upon the problem : ...
Batman's user avatar
  • 1
0 votes
0 answers
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$$)$ ...
JORGE's user avatar
  • 259
4 votes
3 answers
1k 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? ...
Xiagua's user avatar
  • 143
1 vote
0 answers
515 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 ...
Crystal's user avatar
  • 11
0 votes
0 answers
15 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?
Mithraasmi's user avatar
0 votes
0 answers
48 views

Complexity of this function [duplicate]

I have this function ...
Jhonny's user avatar
  • 1
3 votes
1 answer
317 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 ...
Milano's user avatar
  • 349
0 votes
0 answers
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: ...
RajS's user avatar
  • 1,667
-1 votes
1 answer
3k 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. ...
Rizwan Ahmed's user avatar