The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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

A list of n strings lexicographic order using the merge-sort algorithm. The worst case running time of this computation is [closed]

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is __________. $O(n log n)$ $O(n^2 log n)$ $O(...
6
votes
1answer
394 views

Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of ...
6
votes
1answer
411 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 ...
4
votes
1answer
3k views

Amortized time cost of insertion into an Array list

A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied ...
4
votes
2answers
144 views

Efficient N-Ary GCD Algorithm

Are any algorithms known that can compute the greatest common denominator of multiple (more than two) input values more efficiently than just an iterative application of the fastest GCD algorithm for ...
4
votes
1answer
71 views

Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?

If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to ...
3
votes
7answers
4k views

Checking if there are 2 elements in an array that sum to X in O(n lg n)

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this ...
3
votes
1answer
567 views

Number of iterations of the Euclidean algorithm

I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says: The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations. Since $...
2
votes
1answer
417 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: ...
2
votes
1answer
2k views

Base of logarithm in runtime of Prim's and Kruskal's algorithms

For Prim's and Kruskal's Algorithm there are many implementations which will give different running times. However suppose our implementation of Prim's algorithm has runtime $O(|E| + |V|\cdot \log(|V|)...
2
votes
1answer
2k views

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
2
votes
2answers
2k views

Running time of selection sort

I wrote pseudocode for Selection Sort, but I'm not sure what is the running time of my algorithm, can you help me with that? My Pseudocode: Selection Sort(int a[], ...
2
votes
2answers
418 views

Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
2
votes
3answers
67 views

Confusion with the Running Time of an algorithm that finds duplicate character

I have the following simple algorithm to find duplicate characters in a string: ...
2
votes
2answers
214 views

Complexity of an algorithm for bounding a region in 2D

First I apologize if the title is unclear, but I didn't find anything better. I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real ...
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 ...
1
vote
1answer
763 views

does cpu time reflect BigO time complexity

QUESTION does CPU time reflect Big O time complexity? WHAT I MADE I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative ...
1
vote
1answer
1k views

Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
0
votes
1answer
465 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
0
votes
3answers
173 views

How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...
0
votes
2answers
1k views

how to calculate time complexity of non terminating loops

I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs. I just wondered that how to calculate time complexity of non terminating ...
0
votes
1answer
62 views

Converting a algorithm to a runtime function

I need to find an upper limit for the runtime of $f(n)$. ...
0
votes
1answer
141 views

Does my Algorithm Qualify as MergeSort?

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...