Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
106
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
554 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 <...
7
votes
0answers
426 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
325 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 ...
7
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 ...
4
votes
0answers
47 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
45 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
929 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
42 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
779 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
190 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
4k 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
131 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
78 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
348 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
172 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
249 views
Analysing Dijkstra Algorithm by using different varieties of Data Structure
Question
I want to analyse Dijkstra Algorithm by using different varieties of Data Structure.
My solution
Adjacency matrix to Store the Graph and Binary heap for Priority Queue.
$...
2
votes
0answers
418 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
181 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
296 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
583 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
61 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
602 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
1answer
39 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
73 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
30 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
62 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 ...
1
vote
0answers
58 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
189 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
19 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
88 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
114 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
343 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
65 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
164 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}$$
...
1
vote
0answers
45 views
Find fastest sort for given range of numbers
I encountered a question from a test that I cant understand the answer
given a range of numbers $[0...(logn)^{logn}-1]$ we need to find the quickest sort available and give his running time
now ...
1
vote
0answers
116 views
Why does this algorithm not have an exponential complexity?
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf
The authors present a PTAS algorithm that can ...
1
vote
0answers
59 views
Big-Oh of algorithm
I found an algorithm which sorts the digits of a number to its smallest form. IE 54321 ==> 12345.
The algorithm looks like:
...
1
vote
0answers
125 views
Does such an algorithm exist? What would the complexity for it be?
Given an $n \times m$ matrix $A$ where
$m-n=1$
The value of any $A$[$i,j$] is either $1$ or $0$
If $A$[$i,j$] $=1$ then $i<j$
Does anyone know of an algorithm which would run as follows and what ...
1
vote
0answers
556 views
Run time of Dijkstra's compared to Kruskal's algorithm using union-find
I am dealing with the following statement:
the run time for Dijkstra's on a connected undirected graph with positive edge weights using a binary heap is $\Theta$ of the run time for Kruskal's using ...
1
vote
0answers
413 views
Bridge Crossing Problem Proof?
I'm trying to find an optimal solution that will work for the bridge crossing problem. In case you don't know it you can check out the Ted Ed video on it. They show how you can do it with 5 people but ...
1
vote
0answers
276 views
How to determine big O of a variable loop
I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the ...
1
vote
0answers
241 views
Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2
Here is a divide and conquer approach for finding minimum and maximum elements in an array.
...
1
vote
0answers
587 views
1
vote
0answers
78 views
Minimum exchanges for heap sort
I'm studying heap sort and was presented with the following question.
What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N? Give a ...
1
vote
0answers
76 views
Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )
You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively.
Assume that you have to choose ...
1
vote
0answers
52 views
Given an algorithm, what are the probabilities for its run-time cases?
I am given this algorithm
And I am also given the fact that $1 \leq k \leq n$.
If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
