Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
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
547 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
417 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
320 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
41 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
44 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
904 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
775 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, ...
2
votes
0answers
91 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
77 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
302 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
165 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
218 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
391 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
172 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
277 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
568 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
58 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
583 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
70 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
28 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
56 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
50 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
145 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
73 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
0answers
138 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
63 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
159 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
42 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
114 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
123 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
542 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
383 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
268 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
230 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
573 views
1
vote
0answers
77 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
75 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
50 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 ...
1
vote
0answers
58 views
Is this Time analysis strategy right?
I'm working in the time analysis for an algorithm with two optional optimizations variant applied and followed next approach:
Create inputs of different lengths for the algorithm
Using these inputs ...
1
vote
0answers
341 views
Influence of edge number and priority-queue implementation on the runtime of Dijkstra
When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
1
vote
0answers
120 views
Is it possible to analyse computation?
Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation.
So you have a ...
0
votes
0answers
9 views
How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?
I am building N-Queen Solver with java.
I confused with AC-3 algorithm.
I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
0
votes
0answers
26 views
Choosing algorithms and/or data structures at runtime based on input characteristics
I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
0
votes
0answers
38 views
Reccurent runtime
If $T(n) = T\left(\frac{n}{2}\right) + 5$ (binary search), then the runtime in Big-O notation is $O(\log(n))$.
If $T(n) = T\left(\frac{n}{2}\right) + 0$, then is it correct to say that the the ...
