# Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

804 questions
Filter by
Sorted by
Tagged with
364 views

### Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
2k views

### Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? [duplicate]

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and ...
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. ...
1k views

### Expected number of updates of minimum

I came across the following problem in a exam. We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ ...
16k views

### What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
149 views

### Complexity of a nested for loop [duplicate]

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows: What value is returned by the following function? Express your ...
107 views

### Analysis of Algorithms: Applying Concepts [duplicate]

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application. I ...
147 views

### Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows: Suppose that a hashing strategy is designed so that it ...
1k views

### Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
900 views

### Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm :...
209 views

### What's the time complexity of this append method? [closed]

I made a method that appends a sequence to another sequence. So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6] CODE In C# ...
1k views

### Relation between space and time complexity for machines with write once read many (WORM) memory

While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A ...
99 views

### The number of executions of the count statement; how many?

How many times does the statement count in line 5 executes in terms of $n$? ...
2k views

### Are there dynamic programming examples that run in exponential time?

Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and ...
5k views

### How to find the cost of pseudocode with a nested loop and a nested if statement?

How can I find the cost of pseudocode with a nested loop and a nested if statement? On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I ...
420 views

### Complexity of keeping track of $K$ smallest integers in a stream

I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is Suppose the $i$th number in the stream is $S_i$. Keep ...
45 views

### Understanding expected time bound for unsuccessful search in R-way tries

As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please ...
120 views

### Runtime analysis of a recursive algorithm with a tricky amount of work per recursive call

I want to analyze the runtime of this algorithm: ...
380 views

### Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...
390 views

### Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst case,...
777 views

### Bubble sort complexity [duplicate]

So I have this code: ...
180 views

### Runtime analysis of a “find the secret number” algorithm

The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='. Find the secret number with <...
4k views

### Complexity analysis of while loop with two conditions

I am curious how to do a line by line analysis of this piece of code using the "Big O" notation. ...
867 views

### How to find the asymptotic runtime of these nested loops? [duplicate]

i=n; while(i>0) { k=1; for(j=1;j<=n:j+=k) k++; i=i/2; } The while loop has the complexity of $\lg(n)$ the j value of inner loop runs 1,3,6,10,15.....
159 views

75 views

### How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?

I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ...
360 views

### Confusion regarding several time complexities including the logarithm

I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is: We use $O(\log n)$ complexity when there is division of any $n$ number on each ...
673 views

### Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
209 views

### Time Complexity of Algorithm

I need help with finding out the time complexity of the following algorithm: ...
161 views

### Runtime of various versions of binary search

I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python) ...
9k views

### Time Complexity for Creating a Graph from a File

Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example: ...
218 views

### Measuring time complexity of algorithm

I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not. I need to find the time complexity for: ...
418 views

### Finding asymptotically tight bounds $\Theta$ of two procedures

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this: ...
2k views

### Time complexity of a triple nested for loop for ThreeSum problem [duplicate]

I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function: ...
619 views

### How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?

A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set ...
Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$ and $q$ , respectively. Each bit in the string is independent of any other bit. ...