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.

learn more… | top users | synonyms

3
votes
1answer
50 views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
-1
votes
0answers
24 views

What are the Correct Conditions for Akra-Bazzi Master Theorem? (Cross-Post) [on hold]

NOTE: this question is cross-posted see original here: http://math.stackexchange.com/q/1767062/327486 Computational Science: http://scicomp.stackexchange.com/q/23888/20247 I deleted this post for ...
1
vote
0answers
16 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
8 views

complexity of incrementally creating a graph [duplicate]

What is the complexity of the two functions f() and g()? They both build a graph G(V, E) incrementally, I think that they are both O(|V|)? f(n): 1. start with an initial graph K3 (triangle); 2. for ...
1
vote
1answer
16 views

Algorithm to convert rendered number back into symbolic form

If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools: 1- ISC 2- wolframalpha and the answer is $\sqrt2+\sqrt3$ I am ...
0
votes
1answer
39 views

Are all problems approached and solved in fundamentally the same way?

This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot. This questions stems from a conversation a friend and I were having ...
-1
votes
2answers
54 views

Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...
2
votes
1answer
83 views

Can RadixSort be Ω(n log n)?

I read about RadixSort and its time complexity and the worst best and average time Complexity is O(n) , so my question is can radixSort be Ω(n log n)?
0
votes
2answers
82 views

What is the time complexity of this algorithm?

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed: She represented the cost of the algorithm by the following sum: ...
1
vote
2answers
58 views

Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve ...
1
vote
0answers
90 views

When does Branch and Bound exactly stop giving solutions for the bin packing problem

I wrote a branch and bound algorithm for the bin packing problem and now I would like to know when exactly it stops giving solutions in a polynomial time. I have N items (each item i has a volume ...
5
votes
1answer
67 views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
3
votes
2answers
95 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 ...
1
vote
0answers
51 views

Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

Here is a divide and conquer approach for finding minimum and maximum elements in an array. ...
8
votes
1answer
64 views

What is the complexity of a bracketed search using mediants?

I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / ...
0
votes
1answer
40 views

Showing that an algorithm is 2-approximation

I'm having trouble showing that this algorithm is 2-approx. We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the ...
3
votes
2answers
488 views

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
2
votes
1answer
48 views

Costs of updating arrays to contain only zeroes

To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also? And in that case, ...
1
vote
2answers
38 views
3
votes
1answer
27 views

What to infer about maximum height of AVL tree from these three different formulae

I have came across following problem: What is the maximum height of any AVL-tree with 7 nodes? The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows: ...
0
votes
2answers
27 views

What is the asymptotic running time of the following piece of code? [duplicate]

I am working with this problem: What is the asymptotic running time of the following piece of code? ...
5
votes
1answer
56 views

How to find time complexity for functions in lazy functional languages?

So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict ...
1
vote
0answers
45 views

Runnig time analysis for algorithem that merges $k$ sorted arrays to one sorted array

Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$ I the first step we will merge ...
4
votes
1answer
52 views

Summation of a Random Variable

I'm having trouble grokking Cormen's Algorithms book on pg. 120. The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up: "Let X be the random ...
0
votes
0answers
31 views

Frequency count of while loop [duplicate]

I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count ...
-2
votes
0answers
18 views

Cost of inserting a sequence of numbers into a BST one by one and then right-rotating all

Is the best case time complexity for a procedure that inserts one by one a sequence of numbers into a BST and then that right-rotates the nodes(all of them) of the BST Θ(n), average case Θ(n logn) and ...
1
vote
1answer
79 views

How to find longest recurring pattern from lage string data set?

I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example ...
2
votes
1answer
107 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
0
votes
0answers
32 views

Is this sorting algorithm valid and able to run in O(range of input set) time?

I imagined a sorting algorithm that sorts an array in O(r) time, where r is the range. Is this already an algorithm (if so, which?), or have I made a mistake calculating the running time (probably). ...
0
votes
0answers
26 views

How do I make the “+2” go away in the recurrence relation of T(n) = 4T(n/2 + 2) + n [duplicate]

$T(n) = 4T(n/2 + 2) + n$ How can I make the plus 2 disappear? I have been reading the answer to this and I'm having trouble understanding it. Can someone maybe show me step by step how I would do ...
3
votes
3answers
395 views

Are there adversarial inputs for randomized quicksort?

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort ...
0
votes
2answers
389 views

how to calculate time complexity of non terminating loops

I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs. I just wondered that how to calculate time complexity of non terminating ...
3
votes
1answer
57 views

Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation: ...
-3
votes
0answers
9 views

big o complexity analysis of dependent nested loops [duplicate]

for(i=0;i<=n;i++) { for(j=0;j please help me in finding complexity of this nested loop.... the outer loop is executing n times and inner loop is dependent on the value of i. so what will be its ...
3
votes
1answer
44 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
3
votes
1answer
62 views

How to come up the number of nodes on a given level in heaps?

CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove ...
5
votes
2answers
71 views

Why does the recurrence equation for QuickSort considers all the elements in the array?

I have been taught that QuickSort has the following recurrence equation in the best case: $T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c ...
1
vote
1answer
41 views

Runtime of algorithem when the internal for depend on the external for

I'm trying to find the running time of this pseodocose: int x=0,i,j for (i=1;i<=n;i++) for(j=1;j<=n+r;j=j+i) x=x+j; What I did: First I checked ...
1
vote
2answers
61 views

How to calculate the mergesort time complexity?

Recently while reading a book I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we ...
2
votes
0answers
45 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 ...
9
votes
1answer
61 views

Randomized Meldable Heap - Expected Height

Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert. The question is, what is an expected height of that tree with $n$ nodes? ...
13
votes
3answers
2k views

How long does the Collatz recursion run?

I have the following Python code. ...
1
vote
1answer
54 views

Solving using the master theorem [duplicate]

I am wondering why this $T(n)=3T(n/4)+n⋅lg(n)$ recurrence can be solve by Master Theorem case 3 but this $T(n)=2T(n/2)+n⋅lg(n)$ recurrence can not be solve by Master Theorem what is the difference ...
3
votes
1answer
48 views

Analysing a small recursive algorithm

I need to calculate the complexity of func5, depending on variables $n, m$. func4 is a function whose complexity is $\Theta(n+m)$ ...
6
votes
1answer
143 views

What is the approximation ratio of this randomized algorithm for finding matchings?

I would like to analyze the following algorithm in terms of its approximation ratio. Here is the algorithm: ...
2
votes
1answer
38 views

Optimal Page Replacement Algorithm - If more than one frame will not be used again, which one gets replaced?

This may not make a difference in the end, but not knowing is driving me insane. When using the Optimal algorithm for page replacement, if you need to put something new into a frame and you have more ...
1
vote
2answers
80 views

What is the significance of a Θ-bound on the running time of Mergesort?

While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given: Mergesort takes $\Theta(n \log n)$ compares to ...
3
votes
2answers
75 views

how to prove that nlogn is not Θ(n) without using limits?

i'm studying an algorithms designing and analysis , and i've question about Big-theta how can i prove that nlogn is not Θ(n) without using limits ?