Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
153
questions with no upvoted or accepted answers
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
8
votes
0
answers
235
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\\
\...
- 539
8
votes
0
answers
582
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 <...
- 3,023
7
votes
0
answers
536
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 ...
- 71
7
votes
0
answers
356
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
0
answers
33
views
Polynomial multiplication in finite field without smooth-order roots of unity
I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult.
If I need to compute a ...
- 53
4
votes
0
answers
50
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 ...
- 141
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
3
votes
0
answers
60
views
Running time analysis of Savitch's algorithm
Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC.
Is ...
3
votes
0
answers
52
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) + ...
- 4,371
3
votes
0
answers
262
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 ...
- 151
3
votes
0
answers
357
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 ...
- 31
3
votes
0
answers
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 ...
- 143
3
votes
0
answers
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 ( ...
- 31
3
votes
0
answers
47
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, ...
- 31
3
votes
0
answers
797
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
3
votes
1
answer
319
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 ...
- 31
3
votes
2
answers
7k
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 ...
- 529
2
votes
0
answers
102
views
Why there is $\log n$ factor in time constructible definition?
I saw two different definitions of time constructible functions.
In Sipser (third edt), Definition 9.8, defines $t(n)$ is time constructible if $t(n)\geq O(n \log n)$ and maps $1^n$ to the binary ...
- 358
2
votes
0
answers
50
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 ...
- 5,704
2
votes
0
answers
168
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 (...
- 43
2
votes
0
answers
30
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 ...
- 151
2
votes
0
answers
94
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 ...
- 141
2
votes
0
answers
977
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. ...
- 21
2
votes
0
answers
249
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 ...
- 21
2
votes
0
answers
317
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 ...
- 121
2
votes
0
answers
756
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+\...
- 121
2
votes
0
answers
1k
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$. ...
- 327
2
votes
0
answers
66
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 ...
- 43
2
votes
0
answers
716
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.
...
clay
2
votes
1
answer
242
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'...
- 145
1
vote
0
answers
26
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
1
vote
1
answer
79
views
Time complexity of merging two lists while preserving order
I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
- 11
1
vote
2
answers
26
views
How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?
I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation
so that I can get ...
- 23
1
vote
0
answers
46
views
Plotting time-complexity vs actual run time
To my understanding, the time-complexity of an algorithm is a measure of its actual run time. For instance, an algorithm with a worst-case time-complexity $T(N)=$(constant)$\times N^2+$(lower order ...
- 11
1
vote
0
answers
26
views
Big theta and big 0 bounds for iteration method and Master Theorem
In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
- 111
1
vote
0
answers
34
views
Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?
The given problem is from CLRS, exercise 4.3-2.
Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n))
I decided to prove T(n) ≤ clog(n) and this is the result I got:...
- 11
1
vote
0
answers
31
views
Is there a branch of CS about studying function calls branching?
I know little about computer science. I wrote a function that has some ifs and may call itself recursively.
Is there a branch of computer science that studies these possible branches?
I'd like to ...
- 111
1
vote
0
answers
55
views
Fibonacci Heap that consolidates after every step
The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would ...
- 11
1
vote
0
answers
37
views
Running time of random pivot quicksort on random and sorted arrays
I don't understand why I am getting the following execution times for the quicksort with a random pivot.
Times are in microseconds they are the average of five executions.
Random array: ...
- 11
1
vote
0
answers
105
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,034
1
vote
0
answers
118
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 ...
- 123
1
vote
0
answers
113
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 ...
- 133
1
vote
0
answers
160
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:
...
- 141
1
vote
1
answer
320
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
0
answers
117
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}\...
- 131
1
vote
0
answers
45
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 ...
- 111
1
vote
0
answers
90
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
...
- 11
1
vote
0
answers
532
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]...
- 73
1
vote
0
answers
22
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 ...
- 111