Tagged Questions
1
vote
2answers
77 views
Why don't we scale the cost of memory access when analyzing runtime of algorithms?
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
2
votes
1answer
52 views
Decreasing runs of inner loop in outer loop [duplicate]
I am trying to determine the worst case runtime of this program:
while n > 1
for i = 1,..,n
m = log(n)
n = n/2
Obviously the outer loop runs ...
1
vote
2answers
78 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 ...
1
vote
1answer
197 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 ...
0
votes
1answer
334 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 ...
5
votes
1answer
1k views
A d-ary heap problem from CLRS
I got confused while solving the following problem (questions 1–3).
Question
A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
6
votes
3answers
275 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 ...
1
vote
2answers
896 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
293 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 ...
11
votes
1answer
376 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
160 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.
...
7
votes
2answers
486 views
Hashing using search trees instead of lists
I am struggling with hashing and binary search tree material.
And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
5
votes
3answers
348 views
Complexity of finding the largest $m$ numbers in an array of size $n$
What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
