Questions tagged [runtime-analysis]

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

Filter by
Sorted by
Tagged with
4
votes
2answers
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 ...
0
votes
2answers
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 ...
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. ...
5
votes
2answers
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$ ...
6
votes
3answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
-1
votes
2answers
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 ...
2
votes
1answer
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: ...
0
votes
1answer
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 :...
-1
votes
1answer
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# ...
5
votes
1answer
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 ...
0
votes
1answer
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$? ...
5
votes
3answers
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 ...
0
votes
2answers
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 ...
7
votes
2answers
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 ...
1
vote
1answer
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 ...
7
votes
1answer
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 ...
3
votes
1answer
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,...
1
vote
1answer
777 views
1
vote
1answer
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 <...
2
votes
1answer
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. ...
0
votes
1answer
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.....
5
votes
1answer
159 views

Largest set of vertices that is larger than its set of neighbors

I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$. For every subset $X' \subseteq X$, they define $$...
1
vote
0answers
14k views

Best and worse case inputs for heap sort and quick sort? [duplicate]

So given a input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
1
vote
3answers
1k views

Worst run-time for 3 nested loop

Suppose we need to find a tight asymptotic bound on the worst case run time of the following program ...
0
votes
1answer
3k views

What is the complexity of this bubble sort algorithm? [duplicate]

I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$ This bubble sort however is slightly more efficient. I thought this ...
3
votes
3answers
281 views

When does an algorithm run in $O(1)$ time?

When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it ...
2
votes
1answer
257 views

Big O and program calls with varied input sizes

Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can ...
0
votes
2answers
93 views
1
vote
1answer
1k views

Sum number of times statement is executed in triple nested loop

I have this code fragment: for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) for( k=0; k<j; k++ ) S; I need to find the number of times ...
6
votes
1answer
414 views

Do different variants of Mergesort have different runtime?

One of my courses introduced the following question: Given the recurrence relation for mergesort: $T(n) = 2T(n/2) + n$ How would the following parameter passing strategies influence the ...
0
votes
1answer
97 views

experimental analysis of running times in extendable table [closed]

I was given the following homework question: Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running ...
1
vote
1answer
3k views

How to analyze/test a binary search algorithm?

I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log ...
3
votes
1answer
1k views

Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

Here is my approach First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: http://en.wikipedia....
2
votes
2answers
183 views

Deriving the exact number of execution times

So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions. Here's a screen cap: The ...
4
votes
1answer
1k views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
-1
votes
1answer
209 views

Time Complexity of Algorithm

I need help with finding out the time complexity of the following algorithm: ...
1
vote
1answer
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) ...
3
votes
1answer
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: ...
1
vote
2answers
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: ...
2
votes
1answer
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: ...
1
vote
1answer
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: ...
6
votes
2answers
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 ...
1
vote
1answer
545 views

Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

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. ...
3
votes
1answer
820 views

Theta Runtime of Nested for Loops

I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much <...