A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [algorithm-analysis]

Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

262 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
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
0answers
157 views

What is the proof for the lemma “For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge”?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
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 ...
6
votes
0answers
227 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how many permutations would get rejected ...
6
votes
0answers
1k views

Choosing potential function in amortized analysis

How should I think to choose the potential function in the amortized analysis? More specifically are there techniques or tips for choosing optimal or good potential functions?
5
votes
0answers
146 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 ...
5
votes
0answers
50 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u \...
5
votes
0answers
1k views

Alpha beta algorithm with Iterative Deepening analysis

I'm implementing a chess engine. Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
5
votes
0answers
72 views

What are the properties of the unsided fold?

Foldl and folr are 2 very important functions for FP and Haskell, but I have never heard much about the unsided fold: fold f [a,b,c,d] = (f (f a b) (f c d)) That ...
4
votes
0answers
73 views

Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
4
votes
0answers
108 views

Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$. The obvious naive way ...
4
votes
0answers
63 views

How advanced is the study of mathematically determining computational power comsumption?

I was thinking about how effective it would be to calculate the number of CPU instructions a section of code would have and then trying to estimate the energy cost for a program. But I was curious if ...
4
votes
0answers
668 views

What is the complexity of Hoffman and Pavley's Nth best path algorithm?

I am currently working on a project where I'm using an implementation of Hoffman and Pavley's "Method for the Solution of the Nth Best Path Problem" to find n-th best path through a directed graph. ...
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
149 views

Analysis quickselect: Median of Medians with duplicates

in This Lecture Notes 1 (page 3), it is said concerning quickselect with median of medians: If there are repeated elements ... Alternatively, one has to refine the algorithm and the analysis ...
3
votes
1answer
184 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
3
votes
2answers
194 views

Invariant on “Find K Closest Elements” problem

I run across this problem: Given a sorted array, two integers k and x, find the k closest ...
3
votes
0answers
38 views

Is it possible, at least in theory, to “lockfree-ize” algorithms algorithmically?

The problem emerged from a practical case, but thinking on it resulted more and more theoretical directions. Typically, the lock-free algorithms do relative simple things in the practice, but their ...
3
votes
0answers
118 views

Will quantum computers out-scale classical computers at P-problems?

It is my understanding that quantum computers have gained interest, because some interesting problems are suspected to be in the BQP-class, but not in the P-class (integer factorization, ...). Quantum ...
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
964 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
219 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
3
votes
0answers
59 views

Is there a known worst start configuration for Ford-Johnson sorting algorithm?

By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items. ...
3
votes
0answers
176 views

Gradient descent vs. Newton's method: which is more efficient?

Using gradient descent in d dimensions to find a local minimum requires computing gradients, which is computationally much faster than Newton's method, because Newton's method requires computing both ...
3
votes
0answers
114 views

Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf Recall that Paxos is a distributed system algorithm with the goal that the processes ...
3
votes
0answers
1k views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
3
votes
0answers
369 views

Expected depth of modified kind of treap

If we have $n$ elements $s_1, \dots, s_n$ and build a kind of treap (tree-heap) out of it. Each $s_k$ has a priority, which is an integer in $\{ 1, 2, 3 \dots, \lceil \log n \rceil\}$. Since the ...
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
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
33 views

When does knowing the number of solutions help (improve the running time)?

Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm ...
2
votes
1answer
46 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
2
votes
0answers
171 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
43 views

Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
2
votes
0answers
98 views

how to find the depth of a concurrency bug

How to find the depth of a concurrency bug The below program runs on two separate threads and shares the variable x. Variables t1 and t2 are local to their threads. The program has a concurrency bug ...
2
votes
0answers
241 views

Analysis expected depth of a binary search tree given random values?

I have a guess about the problem above. Suppose I have a binary search tree $T$ initially empty. Suppose I drawn $x_1,\ldots,x_k$ (from some real interval $[a,b]$) keys and I want to insert the keys ...
2
votes
0answers
35 views

Sorting Algorithm: Probability Bound For Randomized Inversion Swapping

Let $A = (a_1, a_2, \dots, a_n)$ denote an array of distinct values with an order defined. Consider the following randomized sorting algorithm. Let $m := 0$. Select a pair $(i, j)$ with $1 \le i < ...
2
votes
1answer
230 views

A* 8-puzzle problem worst case memory usage

We are testing the A* algorithm with Hamming and Manhattan on the 8-puzzle (and its natural generalization n-puzzle) problem. We have to answer the following question but I can't figure out what it ...
2
votes
0answers
160 views

Sedgewick analysis of algorithm, difference between theory of algorithm and scientific approach

I'm trying to improve my skills in analysis of algorithms. I think Sedgewick's "introduction to the analysis of algorithm" is a good, I'm reading carefully the first chapter, at least I'm trying. And ...
2
votes
0answers
22 views

Comparison of Swarm Intelligence Algorithms with Constraint Violations

I want to compare swarm intelligence algorithms in a optimisation problem. As far as I understand, a typical approach is to perform several runs of each algorithm (say 30 independent runs, with ...
2
votes
0answers
68 views

Formal justification of the accounting method and its meaning

I'm reading through CLRS again and I was wondering if there's a formal justification or construction of the accounting method, explaining why it works. For some reason it seems to me that CLRS ...
2
votes
1answer
1k views

Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
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
93 views

Maximum value reached in extended binary GCD

Given positive integer inputs $x$ and $y$ , with $0<x<y$ and $y$ an odd prime (or $\gcd(x,y)=1$ and $y$ odd), the following algorithm computes $x^{-1}\bmod y$ per the (half-)extended binary GCD. ...
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
136 views

How to solve a knapsack problem using a modified version of DP?

Im having difficulties understanding how to solve the knapsack problem using dynamic programming, where v is value and w is the weight, where I can fill up to a maximum weight j for some Capacity_J: <...
2
votes
0answers
437 views

Greedy max k-cut approximation algorithm

I'm trying to formulate a greedy algorithm for the Max k-cut problem: Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all ...
2
votes
0answers
45 views

Proving number of comparisons in insertion and bubble sort

I was able to come up with few examples where number of comparisons in insertion sort were fewer than that of bubble sort and some examples where they were same. However I am not able to prove that ...