Questions tagged [algorithm-analysis]
Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.
1,948
questions
4
votes
1
answer
122
views
Computing the running time of a divide-by-4-and-conquer algorithm
I write this code in python:
...
- 2,181
7
votes
2
answers
7k
views
Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?
I am reading section 6.4 on Heapsort algorithm in CLRS, page 160.
...
- 461
2
votes
1
answer
184
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, ...
- 493
2
votes
1
answer
4k
views
Finding the number of leaves in a imbalanced recursion tree
I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00.
So we have a recursion formula
$\qquad T(n) = T(n/10) + T(9n/10) + O(n)$
If we build a recursion tree ...
user1671022
9
votes
3
answers
31k
views
Big O: Nested For Loop With Dependence
I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
user1000229
9
votes
3
answers
4k
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 ...
- 255
4
votes
0
answers
2k
views
Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs
This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
- 309
13
votes
2
answers
20k
views
6
votes
1
answer
389
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 ...
- 201
6
votes
3
answers
552
views
Good text on algorithm complexity
Where should I look for a good introductory text in algorithm complexity? So far, I have had an Algorithms class, and several language classes, but nothing with a theoretical backbone. I get the whole ...
- 215
19
votes
3
answers
3k
views
Why use comparisons instead of runtime for comparing two algorithms?
I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
- 361
7
votes
0
answers
360
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 699
4
votes
2
answers
10k
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.
...
- 255
0
votes
1
answer
2k
views
How to calculate the depth of sorting networks?
I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.
For example, in case of selection sort, we have:
$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$
...
Steven
3
votes
0
answers
799
views
Analysis of a linear-time algorithm for longest palindromic substring
Background
$\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, ...
- 621
11
votes
1
answer
903
views
Bound on space for selection algorithm?
There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
- 829
11
votes
1
answer
1k
views
Tighter analysis of modified Borůvka's algorithm
Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.
The pseudo-code is:
...
- 4,047
1
vote
2
answers
737
views
Existence of a route following one-way streets
I am trying to understand the approach for this problem:
"If all streets are one way, there is still a legal way to drive from
one intersection to another"
The question is to prove that it can ...
- 111
14
votes
1
answer
16k
views
Expected number of swaps in bubble sort
Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
TheRock
7
votes
4
answers
3k
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 ...
- 775
2
votes
1
answer
4k
views
Time complexity of a triple nested loop with squared indices
I have seen this function in past year exam paper.
...
- 775
17
votes
1
answer
3k
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 ...
- 623
9
votes
1
answer
1k
views
Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
- 261
4
votes
1
answer
218
views
Is the following recurrence for this program's runtime correct?
Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:
...
- 41
7
votes
0
answers
191
views
What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?
For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
- 261
6
votes
2
answers
2k
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.
...
- 63
19
votes
4
answers
5k
views
Recurrences and Generating Functions in Algorithms
Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex ...
- 3,857
3
votes
1
answer
8k
views
Quicksort to find median?
Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers?
If your algorithm continually picks a number larger than or smaller than all ...
user1422
1
vote
1
answer
409
views
Recursion for runtime of divide and conquer algorithms
A divide and conquer algorithm's work at a specific level can be simplified into the equation:
$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$
where $n$ is the size of ...
user1422
84
votes
6
answers
21k
views
How can we assume that basic operations on numbers take constant time?
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
user742
6
votes
1
answer
902
views
Master theorem and constants independent of $n$
I applied the Master theorem to a recurrence for a running time I encountered (this is a simplified version):
$$T(n)=4T(n/2)+O(r)$$
$r$ is independent of $n$. Case 1 of the Master theorem applies ...
- 8,986
4
votes
2
answers
3k
views
Running time - Linked Lists Polynomial
I have developed two algorithms and now they are asking me to find their running time.
The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are ...
- 787
8
votes
1
answer
8k
views
Finding a worst case of heap sort
I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest.
The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift ...
- 2,181
3
votes
1
answer
3k
views
Magic Square Check for NxN Matrix - with Minimum Complexity?
Is there any algorithm that works better than $\Theta(n^2)$ to verify whether a square matrix is a magic one? (E.g. such as sum of all the rows, cols and diagonally are equal to each other).
I did ...
- 221
9
votes
1
answer
7k
views
How to use adversary arguments for selection and insertion sort?
I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.
I have some doubts regarding this. I ...
- 2,161
10
votes
1
answer
2k
views
Lower bound for finding kth smallest element using adversary arguments
In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument?
Wikipedia says that tournament ...
- 2,161
16
votes
4
answers
10k
views
Quicksort explained to kids
Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper.
Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or ...
- 2,181
6
votes
3
answers
9k
views
Quicksort vs. insertion sort on linked list: performance
I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm.
Does anyone have any idea why this is?
Insertion sort has a ...
- 787
11
votes
1
answer
197
views
Sharp concentration for selection via random partitioning?
The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:
Sample $n^{3/4}$ elements from $A$ with replacement into $B$
Sort $B$ and find the rank $|B|\pm \sqrt{n}$ ...
- 2,906
14
votes
1
answer
7k
views
Randomized Selection
The randomized selection algorithm is the following:
Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$
Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
- 431
3
votes
1
answer
2k
views
Solve a recurrence using the master theorem
This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem:
$$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$
I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^...
- 133
10
votes
3
answers
2k
views
The space complexity of recognising Watson-Crick palindromes
I have the following algorithmic problem:
Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.
Watson-Crick palindromes are strings whose reversed ...
- 425
9
votes
2
answers
9k
views
How does the NegaScout algorithm work?
On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1].
I do not understand the whole process of NegaScout.
How does it work? What is ...
- 339
9
votes
1
answer
1k
views
Solving Recurrences via Characteristic Polynomial with Imaginary Roots
In algorithm analysis you often have to solve recurrences. In addition to Master Theorem, substitution and iteration methods, there is one using characteristic polynomials.
Say I have concluded that ...
- 221
10
votes
3
answers
6k
views
Logarithmic vs double logarithmic time complexity
In real world applications is there a concrete benefit when using $\mathcal{O}(\log(\log(n))$ instead of $\mathcal{O}(\log(n))$ algorithms ?
This is the case when one use for instance van Emde Boas ...
- 283
73
votes
4
answers
33k
views
(When) is hash table lookup O(1)?
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
40
votes
5
answers
119k
views
How to come up with the runtime of algorithms? [duplicate]
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.
I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
- 523
24
votes
2
answers
337
views
Is Smoothed Analysis used outside academia?
Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
user20