Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
159
votes
3answers
17k 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 ...
35
votes
5answers
100k 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 ...
70
votes
4answers
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 ...
10
votes
4answers
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" ...
18
votes
3answers
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. ...
19
votes
2answers
5k views

How to describe algorithms, prove and analyse them?

Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
17
votes
5answers
2k views

For what kind of data are hash table operations O(1)?

From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...
13
votes
2answers
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 ...
5
votes
2answers
1k 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 ...
6
votes
2answers
5k views

Proving the lower bound of compares in comparison based sorting

I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help ...
4
votes
2answers
9k 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. ...
3
votes
2answers
4k views

Using software to calculate the complexity of an algorithm

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
34
votes
2answers
10k views

Why is the log in the big-O of binary search not base 2?

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
8
votes
2answers
813 views

What constitutes one unit of time in runtime analysis?

When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
3
votes
1answer
379 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst case,...
6
votes
3answers
16k views

What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
1
vote
2answers
868 views

How does the automatic complexity analysis of Codility work?

When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code. I was just wondering how ...
15
votes
3answers
5k views

Brzozowski's algorithm for DFA minimization

Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by: reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N&#...
9
votes
3answers
21k views

Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
4
votes
2answers
999 views

Why does linear search have $\frac{n}{2}$ comparisons on average?

I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons. I tried working this out on my own. First I considered the number of cases. ...
4
votes
2answers
193 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 ...
3
votes
2answers
3k views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
4
votes
2answers
681 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 ...
4
votes
1answer
801 views

how to understand time complexity from a plot?

This is my first question here. I'm not a CS at all, so it might be quite trivial. I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear ...
2
votes
2answers
829 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
2
votes
1answer
484 views

Precise runtime of the algorithm to find number of digits in an integer

Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm ...
2
votes
1answer
1k views

Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
1
vote
0answers
377 views

Help with deterministic selection algorithm

All we know what is Deterministic Selection Algorithm: Line up elements in groups of five (this number $5$ is not important, it could be e.g. $7$ without changing the algorithm much). Call each group ...
1
vote
1answer
366 views

Euclid's Algorithm Time Complexity

I have a question about the Euclid's Algorithm for finding greatest common divisors. gcd(p,q) where p > q and q is a n-bit integer. I'm trying to follow a time complexity analysis on the algorithm (...
1
vote
2answers
624 views

Average-Case Analysis of a Simple Max-Finding Algorithm

Given this piece of code: ...
0
votes
0answers
48 views

Complexity of this function [duplicate]

I have this function ...
36
votes
3answers
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 ...
48
votes
3answers
22k 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'...
32
votes
3answers
40k views

What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
2
votes
1answer
3k views

Time complexity of a triple nested loop with squared indices

I have seen this function in past year exam paper. ...
10
votes
3answers
20k views

A d-ary heap problem from CLRS

I got confused while solving the following problem (questions 1–3). Question A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 ...
10
votes
2answers
12k 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 ...
9
votes
1answer
5k views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...
4
votes
1answer
9k 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: ...
13
votes
1answer
2k views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
6
votes
1answer
4k views

What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "...
5
votes
1answer
319 views

Why don't we emphasize “length of input string” when considering time complexity of sorting algorithms?

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$. However, why don't we ...
2
votes
1answer
161 views

Pseudo code algorithm for beauty contestant question

Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria. ...
2
votes
1answer
56 views

What is the complexity to show this theorem?

Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1). There is need to show that the sum of all regular expressions is either equal to ...
10
votes
2answers
458 views

Multiplication in $O(n\cdot \log n)$

I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot ...
4
votes
2answers
2k 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: ...
3
votes
1answer
6k 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 ...
3
votes
2answers
601 views

How to solve the recurrence: T(n) = n*T(n-1) + n?

In a an exercise I'm required to analyze the runtime of recursive function: ...
1
vote
1answer
327 views

A plane-sweep algorithm for a points in triangles inclusion problem

I was given the following homework assignment: Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle ...
0
votes
1answer
260 views

Can I speed up Insertion Sort by using a tree for finding insertion positions?

I want to implement an insertionSort-algorithm. Let's say I have these pseudocode. ...