Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
130
questions with no upvoted or accepted answers
9
votes
1answer
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 ...
8
votes
0answers
228 views
Complexity of computer algebra for systems of trigonometric equations
As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence:
$\qquad f_{p_0} = 0\\
\...
8
votes
0answers
570 views
Predecessor query where the insertion order is known
Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and <...
8
votes
2answers
2k views
Time Complexity analysis for Map-Reduce model
I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.
As a ...
7
votes
0answers
473 views
What is the average-case running time of Fun-sort?
I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
7
votes
0answers
337 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 ...
4
votes
0answers
49 views
Highest stack of rectangles
Suppose we have a set of $n$ dimensional rectangles $R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$. We want to create the highest stack in say the first dimension such that each side of the ...
4
votes
0answers
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 ...
3
votes
0answers
48 views
Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm
I have a graph algorithm that runs in:
$$ T(n, m) = \begin{cases}
c_1 & n \leq 2 \lor m = 1\\
T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + ...
3
votes
0answers
1k views
What is the Big-Oh asymptotic complexity of learning in Random Forests?
Random Forests is a bagged ensemble of CART learners. The following is what I've found, but am not sure if I'm completely right.
CART (Classification and Regression Trees) uses the Gini index for ...
3
votes
0answers
1k views
Analysis of Weighted Quick Union with Path Compression
I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function).
I understand why it is $O ( ...
3
votes
0answers
43 views
Running time for threshold function evaluation?
A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows:
$$f(x_1, ...
3
votes
0answers
786 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, ...
3
votes
1answer
230 views
Theoretical worst case running time of finding a path through a maze?
Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the ...
3
votes
2answers
5k views
Best case analysis for Shell sort
The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my ...
2
votes
0answers
44 views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
2
votes
0answers
33 views
trouble solving the recurrence 4T(n/2) + n
I am having trouble figuring out how to solve this recurrence problem...
$$
\begin{aligned}
&4T(n/2) + n \\
= &4(4T(n/4) + n/4) + n \\
= &16T(n/4) + 2n \\
= &4^kT(n/2^k) + kn
\end{...
2
votes
0answers
45 views
How does the maximum number of guesses needed to win Mastermind (board game) change as the size of the board increases?
Donald Knuth demonstrated that the codebreaker in the board game Mastermind can solve the pattern in five moves or fewer using the following algorithm:
Create a set S of remaining possibilities (...
2
votes
1answer
68 views
Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$
In a hypothetical world, we have a machine that can find median of $n$
numbers in $O(\sqrt{n})$. (Of course this machine is not real).
Can we use this machine to sort an array in $O(n)$?
I don'...
2
votes
0answers
22 views
Simulating Boolean Circuit with RAM
Statement:
Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM).
Could you please supply me with a reference to an ...
2
votes
0answers
113 views
How to find big-O for an in-place perfect shuffle algorithm
I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
2
votes
0answers
229 views
Tail recursion can't work with dynamic programming programs
I am doing some exercises on dynamic programming in order to get familar with this concept.
I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
2
votes
0answers
85 views
Examples of context-free grammars with worst-case complexity
What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers?
I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
2
votes
0answers
585 views
One algorithm for turnpike reconstruction problem?
In << Data Structure and Algorithm Analysis >>, turnpike reconstruction problem is given for demo of backtracking.
Suppose we are given n points, p1 , p2 , . . . , pn , located on the X -axis. ...
2
votes
0answers
196 views
How does one heuristically determine if an algorithm has an exponential time complexity?
How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of ...
2
votes
0answers
659 views
Time complexity of the operations on a b-tree if deletion is performed by marking nodes inactive
I'm given a B-tree where the delete-operation is not implemented, but instead keys are deleted using tombstones (so they stay in the tree, but are marked as deleted). Now when at least 90% of all keys ...
2
votes
0answers
255 views
FPT: Dominating Set on Planar Graphs (average degree is known)
I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this:
Dominating Set on Planar Graphs
Instance: A planar graph G and an
integer ...
2
votes
0answers
443 views
Computational complexity of Doolittle's algorithm
I could not find a big-oh cost for Doolittle's algorithm for LU decomposition of a matrix online, so I took a pseudocode implementation from here
and analyzed it to get $$\frac13n^3+\frac32n^2+\...
2
votes
0answers
838 views
DPLL time complexity analysis
Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
2
votes
0answers
65 views
Lower-bounds of running-time for output sensitive Algorithms
Let me ask my general question using a specific example, namely range searching:
Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle.
If the ...
2
votes
0answers
640 views
Why does Shellsort work well on Sorted and Reverse ordered lists?
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
1
vote
0answers
26 views
Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
1
vote
0answers
31 views
Intuition behind the entire (amortized) concept of Fibonacci Heap operations
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The potential function for the Fibonacci Heaps $H$ is defined as follows:
$$\Phi(H)...
1
vote
0answers
13 views
In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
1
vote
0answers
37 views
Clarification of the analysis of the worst case situation of quicksort as dealt with in CLRS
I was going through the text Introduction to Algorithms by Cormen et. al. and I came across their analysis of the worst case of the quicksort algorithm. I could not quite understand a few specific ...
1
vote
1answer
67 views
What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?
I was solving the following problem, just for reference (441 - Lotto). It basically requires the generation all $k$-combinations of $n$ items
...
1
vote
0answers
45 views
Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?
When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.
Using Fibonacci-heaps instead, are we not able to achieve a ...
1
vote
0answers
30 views
How to find the asymptotic bit cost
I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
1
vote
0answers
38 views
Time Complexity of a Naive Solution to Merge K Sorted Arrays
There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following naive solution:
...
1
vote
1answer
122 views
Recursion Time Complexity (Half n' Half)
This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity:
Input: string $s = s_1,\ldots,s_n$, integer $k$
Go over all symbols $s_1,\ldots,s_n$, one by one
...
1
vote
0answers
85 views
Convex hull partition of a set of points
Given a set $S$ of $n$ points in $\mathbb R^2$, denote by $\mathrm{convb}(S)$ the boundary of the convex hull of $S$. Let
\begin{align*}
S_1 &= \mathrm{convb}(S)\\
S_{i+1} &= \mathrm{convb}\...
1
vote
0answers
40 views
Time and space complexity of a recursive problem (code included)
I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from ...
1
vote
0answers
73 views
Upper bound on the average-case runtime of shell sort
I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases.
I want to know the upper bound complexity in average cases, so I write
...
1
vote
0answers
390 views
Complexity of bisection method for finding an interval
Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
1
vote
0answers
20 views
How does the browser
I wondering how the browser's JS runtime implements these methods. I looked on the web and could not find any documentation.
How does something like the V8 runtime actually work to implement these ...
1
vote
0answers
107 views
Randomized meldable heap - meld is oversimplified?
On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps:
...
1
vote
1answer
135 views
Runtime analysis of prime-set computation
I want to find the all primes between 2 and $k-1$. We can come up with an $O(k\log k)$ running time algorithm. I want to compute this set in $O(k)$ running time. For this algorithm is :
we are ...
1
vote
0answers
542 views
Help with deterministic selection algorithm
All we know what is Deterministic Selection Algorithm:
Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
0answers
76 views
A question on analysis of the time complexity of a recursive branching algorithm
I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows:
Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
1
vote
0answers
179 views
Median-of-Medians algorithm, calculating the constant c
I'm having trouble understanding how the calculation of the constant $c$ in the Median-of-Medians-algorithm is build up ($cn$). The only calculation I found was on Wikipedia:
$$\frac{2g(g-1)}{g-3}$$
...
