Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
1,039
questions
5
votes
3
answers
611
views
Why are hash map look-ups assumed to be $O(1)$ on average
To look up a key in a hash map you have to
calculate its hash
find the entry in the resulting hash bucket
Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.
When ...
- 267
5
votes
2
answers
571
views
BigO, Running Time, Invariants - Learning Resources
What are some good online resources that will help me better understand BigO notation, running time & invariants?
I'm looking for lectures, interactive examples if possible.
5
votes
2
answers
418
views
Upper bounds for a binomial coefficient
I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...
5
votes
2
answers
7k
views
DFS vs. Union Find for computing connected components of a static graph
According to CLRS,
When the edges of the graph are static—not changing over time—we can
compute the connected components faster by using depth-first search.
However, I tried to do some runtime ...
- 153
5
votes
2
answers
2k
views
Finding potential function for dynamic array
About dynamic array, doubling it's size with every element that is beying its limit:
From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
- 209
5
votes
2
answers
5k
views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
- 849
5
votes
1
answer
352
views
What is the complexity of an in-place merge algorithm for forward iterators
I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to ...
- 304
5
votes
2
answers
2k
views
How fast can we identifiy almost-duplicates in a list of strings?
I'm having trouble figuring out the upper bound running time for this scenario:
Input:
$N$ number of strings
$M$ upper bound of string length
$T$ threshold for edit distance (2 strings with a ...
- 431
5
votes
1
answer
313
views
What is the runtime of the 'Risch Algorithm'?
I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.
https://en.wikipedia.org/...
5
votes
3
answers
226
views
Why does this mergesort variant not do Θ(n) comparisons on average?
A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:
...
- 53
5
votes
1
answer
899
views
Pruned FFT runtime
Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). ...
- 201
5
votes
1
answer
1k
views
Relation between space and time complexity for machines with write once read many (WORM) memory
While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A ...
- 5,390
5
votes
1
answer
21k
views
Best-Case Running Time For Binary Search Tree Insertion
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:
The term best-case performance is used in computer science to ...
- 205
5
votes
1
answer
88
views
Least number of guesses needed to determine all unknown subsets of a set
Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
- 163
5
votes
2
answers
230
views
What data structure might this game use?
This question is not about game development or about actual implementation details.
I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
- 325
5
votes
2
answers
3k
views
What is the time-complexity of histogram computation?
Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.
Pseudocode:
...
user35624
5
votes
1
answer
176
views
Largest set of vertices that is larger than its set of neighbors
I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$.
For every subset $X' \subseteq X$, they define
$$...
- 5,994
5
votes
1
answer
980
views
Parallel merge sort using hypercube connection template
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.
What I ...
Игорь Морозов
4
votes
4
answers
6k
views
Why is the running time for BFS $O(b^{d+1})$?
In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as ...
- 171
4
votes
4
answers
8k
views
Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?
I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up).
Why does ...
- 1,607
4
votes
1
answer
628
views
Matrix Max in less than O(n)
I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better ...
- 143
4
votes
2
answers
777
views
What is the name of this search algorithm?
I was thinking about an efficient binary search for unsorted arrays with $n$ entirely unique elements, and came up with something that probably already exists. Here's how it works:
At each level of ...
- 143
4
votes
3
answers
26k
views
What is the average time complexity, for a single linked list, for performing an insert?
I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list.
The longer the list, the longer it will take on average to do the ...
- 141
4
votes
3
answers
7k
views
Why can't hash tables provide O(n) sorting?
Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
- 183
4
votes
1
answer
15k
views
Triple nested for-loops [duplicate]
Possible Duplicate:
A puzzle related to nested loops
I am trying to count the exact/total number of iterations the following nested for-loops are executed:
...
- 143
4
votes
3
answers
9k
views
String Comparison vs. Hashing
I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:
Comparing two ...
- 210
4
votes
1
answer
3k
views
Why is a sequence of n Push, Pop, Multipop operations O(n²)?
From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:
Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
- 143
4
votes
2
answers
268
views
Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?
Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is ...
- 1,632
4
votes
2
answers
2k
views
Number of times statement is executed in complex nested loop
I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:
...
- 43
4
votes
1
answer
17k
views
Searching through a heap complexity
Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
- 41
4
votes
2
answers
389
views
Performance impact due to time required for shuffling in Quicksort
As a programmer with non CS background, I am learning algorithms.
When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
- 185
4
votes
1
answer
15k
views
How to prove that average complexity is N/2 for linear search in the unsorted array [duplicate]
All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the ...
- 315
4
votes
1
answer
303
views
How to solve recurrences with transcendental terms?
Problem:
A number is said to be a magic number, if the sum of its digits, taken again and again till it becomes a single digit number, is 1.
Example: $289 => 19 => 10 => 1 => 289$ is ...
- 143
4
votes
3
answers
1k
views
Analyzing the time complexity of nested loops
So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.
What is the time complexity of this code?
...
- 143
4
votes
1
answer
7k
views
Inserting vertex in an adjacency matrix
If a graph with $v$ vertices is represented in the form of adjacency matrix .
Then, adding a new vertex to the existing graph requires how much time ?
Is it $O(v^2)$ or $O(2v)$ .
We have the ...
- 505
4
votes
2
answers
10k
views
Time complexity formula of nested loops
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.
...
- 255
4
votes
1
answer
351
views
How to prove that the time complexity of this algorithm is O($\sqrt{N}$)?
int n;
cin >> n;
int sum = 0;
for (int i = 1; sum <= n; i++) {
sum += i;
}
If I assumed that $N = 100$, the loop will run $13$ steps, ...
- 241
4
votes
1
answer
306
views
Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?
Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time?
Given that $a$ is an infinite ...
4
votes
2
answers
2k
views
Time complexity of matrix multiplication in Big-Align
I am reading the following paper:
Big-Align: Fast Bipartite Graph Alignment. Danai Koutra, Hanghang Tong, David Lubensky. International Conference on Data Mining (ICDM 2013).
I'd like to ...
- 269
4
votes
1
answer
1k
views
Ford-Fulkerson Running Time
This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them!
In the analysis of Ford-...
- 71
4
votes
1
answer
2k
views
Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n
For analyzing the running time of an algorithm , I'm stuck with this recursive equation :
$$
T(n) = \log(n) \cdot T(\log n) + n
$$
Obviously this can't be handled with the use of the Master Theorem, ...
- 270
4
votes
2
answers
719
views
Analysis of algorithms, 'big O' question
The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?
Also, what about ...
user8872
4
votes
1
answer
96
views
Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?
If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to ...
- 225
4
votes
1
answer
6k
views
Amortised analysis of binary heap insert and delete-min
I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.
We can assume, that insert is O(logn) and delete-min is O(logn) too.
The goal is ...
- 339
4
votes
1
answer
1k
views
Why use minhash instead of directly computing Jaccard coefficient?
Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute.
...
- 41
4
votes
1
answer
92
views
About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]
In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations:
$$\begin{gather*}
C_N = N + 1 + (...
- 165
4
votes
1
answer
239
views
Tallest Person Average Memory Updating?
We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint?
A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
- 201
4
votes
1
answer
129
views
Computing the running time of a divide-by-4-and-conquer algorithm
I write this code in python:
...
- 2,219
4
votes
1
answer
222
views
Is the following recurrence for this program's runtime correct?
Let $f$ and $g$ be two functions and $p$ a number. Consider the following program:
...
- 41
4
votes
2
answers
3k
views
Running time - Linked Lists Polynomial
I have developed two algorithms and now they are asking me to find their running time.
The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are ...
- 787