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
vote
1answer
588 views

A plane-sweep algorithm for a points in triangles inclusion problem

I was given the following homework assignment: Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle ...
0
votes
1answer
284 views

Can I speed up Insertion Sort by using a tree for finding insertion positions?

I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ...
-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
418 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 ...
6
votes
1answer
4k 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 ...
6
votes
1answer
445 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 ...
4
votes
2answers
157 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
627 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
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
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
1answer
424 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

Complexity of optimized bubblesort [closed]

What is the runtime complexity of the following implementation of Bubblesort (for integers)? ...
2
votes
3answers
68 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
424 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
2answers
216 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
935 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
57 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 ...
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
3answers
174 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
1answer
143 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 "...
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
496 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 ...

1 2