Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
116
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
560 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
443 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
330 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 ...
5
votes
0answers
143 views
Time Complexity for Nearest Neighbor Searches in kd-trees
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.
In order to calculate the average number of ...
4
votes
0answers
48 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
47 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
963 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
783 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
203 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
1answer
41 views
Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author ...
2
votes
1answer
34 views
number of comparisons in searching algorithms
i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.
For linear search :
...
2
votes
0answers
170 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
72 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 $\...
2
votes
0answers
82 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
455 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
182 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
281 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
517 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
235 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
356 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
690 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
63 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
622 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
10 views
What's the decoding time complexity of LT codes?
LT codes are practical fountain codes that are near-optimal erasure correcting codes.
Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ ...
1
vote
1answer
63 views
Analyzing time complexity of solution in tutorial
Could someone explain time complexity of solution of in this tutorial?
I'm having hard time figuring out, how asymptotic bounds for first solution is $O(3^k k)$.
What I figured so far is, for ...
1
vote
1answer
58 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
76 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
32 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
68 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
66 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
286 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
100 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
121 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
409 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
173 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
48 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
119 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
126 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
590 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
435 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
284 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 ...
