# 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.

1,588 questions
Filter by
Sorted by
Tagged with
18k views

### Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis). Many are similar, for instance those asking for a cost analysis ...
13k views

### How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
16k views

### How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting ...
25k views

### (When) is hash table lookup O(1)?

It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
23k views

### Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'...
7k views

### How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers: ...
7k views

### Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
104k views

### How to come up with the runtime of algorithms? [duplicate]

I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site. I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
4k views

### How is algorithm complexity modeled for functional languages?

Algorithm complexity is designed to be independent of lower level details but it is based on an imperative model, e.g. array access and modifying a node in a tree take O(1) time. This is not the case ...
44k views

### How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
3k views

### How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
1k views

### How asymptotically bad is naive shuffling?

It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly: ...
3k views

### Will hardware/implementation affect the time/space complexity of algorithms?

I’m not even a CS student, so this might be a stupid question, but please bear with me... In the pre-computer era, we can only implement an array data structure with something like an array of ...
8k views

### Is it a problem to be a programmer with no knowledge about computational complexity?

I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess. Then I made ...
27k views

### How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
313 views

### Is Smoothed Analysis used outside academia?

Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?
5k views

### Why is adding log probabilities faster than multiplying probabilities?

To frame the question, in computer science often we want to calculate the product of several probabilities: P(A,B,C) = P(A) * P(B) * P(C) The simplest approach ...
973 views

### Do functions with slower growth than inverse Ackermann appear in runtime bounds?

Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...
4k views

### How long does the Collatz recursion run?

I have the following Python code. ...
10k views

### What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?

Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
2k views

### Why use comparisons instead of runtime for comparing two algorithms?

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
594 views

### How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time. Here is a citation ...
48k views

### Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, ...
7k views

### What is the advantage of Randomized Quicksort?

In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set ...
4k views

### Recurrences and Generating Functions in Algorithms

Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex ...
827 views

### What's harder: Shuffling a sorted deck or sorting a shuffled one?

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (...
10k views

### Quicksort explained to kids

Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper. Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or ...
7k views

### Why don't we use quick sort on a linked list?

Quick sort algorithm can be divided into following steps Identify pivot. Partition the linked list based on pivot. Divide the linked list recursively into 2 parts. Now, if I always choose last ...
3k views

### Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the ...
29k views

### Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list

Most probably, this question is asked before. It's from CLRS (2nd Ed) problem 6.5-8 -- Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total ...
3k views

### Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
7k views

### Randomized Selection

The randomized selection algorithm is the following: Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$ Output: The the "rank $k$ element" of $A$ (i.e., the one in ...
11k views

### Expected number of swaps in bubble sort

Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
5k views

### Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
13k views

### algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
16k views

### Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...
8k views

### What does it mean by saying “Asymptotically more efficient”?

What does it mean when we say that an algorithm $X$ is asymptotically more efficient than $Y$ ? $X$ will be a better choice for all inputs. $X$ will be a better choice for all inputs except small ...
14k views

### Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
7k views

Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits. Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known ...
2k views

### Good mathematical book on algorithms [closed]

I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very ...
666 views

### Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
3k views

### Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm

I am working on string searching algorithms that support multiple pattern search. I found two algorithms that seem like the strongest candidates in terms of running time, namely Aho-Corasick and ...
1k views

### Tighter analysis of modified Borůvka's algorithm

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: ...
158 views

### Sharp concentration for selection via random partitioning?

The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is: Sample $n^{3/4}$ elements from $A$ with replacement into $B$ Sort $B$ and find the rank $|B|\pm \sqrt{n}$ ...
3k views

### Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)? I googled "Automatic algorithm analysis" ...
14k views

### Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
2k views

### The space complexity of recognising Watson-Crick palindromes

I have the following algorithmic problem: Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes. Watson-Crick palindromes are strings whose reversed ...
9k views

### Why is DFS considered to have $O(bm)$ space complexity?

According to these notes, DFS is considered to have $O(bm)$ space complexity, where $b$ is the branching factor of the tree and $m$ is the maximum length of any path in the state space. The same is ...
In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument? Wikipedia says that tournament ...