Tagged Questions
-3
votes
0answers
39 views
Finding a better algorithm for a problem [closed]
Interval scheduling.
Job j starts at sj and finishes at fj
What is the best way to solve this?
1
vote
2answers
173 views
Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
1
vote
2answers
68 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 ...
10
votes
6answers
374 views
What are the characteristics of an $O(n \log n)$ time complexity algorithm?
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
1
vote
2answers
98 views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
2
votes
2answers
139 views
Running time of a nested loop with $\sum i \log i$ term
So I have the following pseudo-code:
Function(n):
for (i = 4 to n^2):
for (j = 5 to floor(3ilog(i))):
// Some math that executes in constant time
So ...
0
votes
1answer
69 views
Computational complexity of the clique problem
What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?
5
votes
2answers
185 views
Advantages of amortized analysis
I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?
What I understood:
Let say we have 3 three operations a,b,c used 1,2 and 3 times ...
1
vote
1answer
180 views
Iterative binary search analysis
I'm a little bit confused about the analysis of binary search.
In almost every paper, the writer assumes that the array size $n$ is always $2^k$.
Well I truly understand that the time complexity ...
-5
votes
1answer
166 views
Comparing Time complexity?
How would I solve these problems involving time complexity:
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs ...
2
votes
0answers
73 views
What is the complexity of Hoffman and Pavley's Nth best path algorithm?
I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
1
vote
2answers
98 views
0
votes
1answer
301 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 ...
4
votes
1answer
236 views
Recurrence relation for time complexity $T(n) = T(n-1) + n^2$
I'm looking for a $\Theta$ approximation of
$$T(n) = T(n-1) + cn^{2}$$
This is what I have so far:
$$
\begin{align*}
T(n-1)& = T(n-2) + c(n-1)^2\\
T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex]
...
2
votes
1answer
68 views
What constitutes one operation/cycle/move in the RAM model?
I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, ...
6
votes
3answers
261 views
Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?
If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get ...
4
votes
2answers
1k views
4
votes
1answer
125 views
What is the complexity of this subset merge algorithm?
Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.
The ...
1
vote
2answers
847 views
Time complexity formula of nested loops
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.
...
3
votes
3answers
285 views
What is the time complexity of this function?
This is an example in my lecture notes.
Is this function with time complexity $O(n \log n)$?.
Because the worst case is the funtion goes into else branch, and 2 ...
10
votes
1answer
338 views
Brute force Delaunay triangulation algorithm complexity
In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the ...
5
votes
2answers
157 views
How to go from a recurrence relation to a final complexity
I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.
...
1
vote
0answers
107 views
complexity of dequeueMax if implemented with unsorted vector [closed]
I am analyzing and testing a priority queue, implemented with a non-standard (non-STL in C++) vector. It is from an assignment of an online course with lots of code supplied: programming assignment 6.
...
