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
Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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\\ \...
user avatar
  • 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 <...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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) + ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ( ...
user avatar
  • 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, ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 (...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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+\...
user avatar
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$. ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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'...
user avatar
  • 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}$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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-...
user avatar
  • 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:...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
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}\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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]...
user avatar
  • 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 ...
user avatar
  • 111