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

0
votes
0answers
13 views

Runtime complexity of TextRank

I am reading a paper [1] about the TextRank algorithm in keyword extraction and they mention the recursive formula: $$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \; \in \; In(V_{i})} \frac{...
9
votes
2answers
141 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 ...
-1
votes
1answer
23 views

Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(...
-1
votes
1answer
105 views

What is the compleixty of this algorithm?

The algorithm is as follows: a = rand % a random number between 0 and 1 b = a while b == a b = rand end Here rand is a ...
1
vote
1answer
51 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 ...
-3
votes
0answers
31 views

How much faster is a server that's 100x faster on a linear-time algorithm? [on hold]

The problem is as follows : A says that his server is 100 times faster than B's server. B's server can execute a program with an input of size n in an a hour. What input size will compute A'server ...
-4
votes
0answers
63 views

How does my main affect the complexity? [on hold]

I have an implementation of Dijkstra with complexity O(MlogN), which i found on Rosetta Code, and i altered the main that now gets the edges from a file and inserts in the adjacency list: ...
1
vote
2answers
44 views

Convergence of recursive formula in TextRank

I am reading a paper about the TextRank algorithm in keyword extraction and they mention the recursive formula: $$ \displaystyle S(V_{i}) = (1 - d) + d \ast \sum_{j \in In(V_{i})} \frac{1}{|Out(V_{j})|...
2
votes
3answers
88 views

Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
3
votes
1answer
30 views

Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
-3
votes
1answer
49 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
-1
votes
0answers
13 views

Give a greedy algorithm(derandomized) for the Maximum directed cut problem achieving an approximation guarantee of factor 1/4 [duplicate]

Maximum directed cut: Given a directed graph G=(V,E) with nonnegative edge costs, find a subset S⊆V to maximize the total cost of edges out of S: cost({(u→v)∣u∈S and v∈S¯}).
1
vote
2answers
36 views

Why should small o notation has to satisfy the equation for all values of the constant

Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the ...
1
vote
5answers
127 views

Why is b-tree search O(log n)?

B-tree is a data structure, which looks like this: If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I ...
4
votes
3answers
138 views

My algorithm is different from CLRS' — is it wrong?

Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states: Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines ...
0
votes
2answers
42 views

With Memoization Are Time Complexity & Space Complexity Always the Same?

I am studying Dynamic Programming using both iterative and recursive functions. With recursion, the trick of using Memoization the cache results will often dramatically improve the time complexity of ...
2
votes
1answer
64 views

Why isn't selection sort O(n log n)?

We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \...
-3
votes
0answers
20 views

Negative amortized cost in stack operation

I have a homework with solution - two stacks A and B manipulated using operations. There is a note It is ok to have a negative amortized cost in the MultiPopA example. Could somebody ...
0
votes
0answers
17 views

Amortised complexity of dynamic array using potential function

I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can ...
6
votes
1answer
103 views

Is EXPTIME “solvable” or “checkable” in exponential time?

According to this video, EXP has problems that are exponentially difficult to check. But according to this video, EXP are problems that are exponentially difficult to solve. It would make sense to ...
-2
votes
1answer
41 views

Complexity and number of bits of square root number

Let an integer a, and b is the number of bits a. 1) If I have a number ...
-1
votes
1answer
34 views

Time complexity for Breadth-First search

I would like to know why the average number of nodes at level d in BFS in a search tree is $\frac{1+b^d}{2}$ as given in this lecture(p.15)?(Here b is the branching factor of the tree and d is the ...
1
vote
0answers
17 views

Wald's equation for dependent decrements

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
3
votes
1answer
37 views

Linearity of Expectation

I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set ...
0
votes
2answers
46 views

Generally, does the time it takes to compute (n mod m) depend on the size of n?

Example: Suppose I have a number a with 100 decimal digits, b with 200 decimal digits, and m with 10 decimal digits. Would the speed of the computation a mod m vary greatly from b mod m because of ...
3
votes
6answers
778 views

Is there a meaningful difference between O(1) and O(\log n)?

A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
2
votes
1answer
34 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
3
votes
1answer
58 views

Why does merging two sorted arrays take 2N - 1 comparisons?

A friend of mine asked me a question on how to prove that merging two sorted arrays requires at least 2N - 1 comparisons Prove that merging two sorted arrays of N items requires at least 2N-1 ...
0
votes
1answer
34 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
0
votes
0answers
29 views

Time complexity of nested for loop function involving mod to filter out the execution [duplicate]

I have to find the time complexity of the following program: ...
-2
votes
1answer
68 views

What is the time complexity of the nested loop ($j=i \ldots n$ inside $i=1 \ldots n$)? [duplicate]

I am looking for the time complexity of the following nested loops, where the inner loop is shrinking. ...
0
votes
1answer
28 views

Runtime analysis with recursion factor

I have this code: if n is even { for i=1....n for j=1...i print j return 8*foo(n/2) } Asking to calculate the running time $T (n)$. I thought at first ...
3
votes
1answer
42 views

Recurrence: space complexity to Tournament Method

Tournament method have this structure to found min and max (function getMinMax): ...
0
votes
1answer
37 views

Space complexity of Horner's method

Following is the excerpt from wiki If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of ...
3
votes
2answers
89 views

Why do we use big O rather than $\Omega$ when discussing best case runtime?

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
3
votes
1answer
91 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
vote
0answers
25 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 ( ...
1
vote
1answer
21 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
40 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 ...
0
votes
2answers
58 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
87 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
85 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: $\sum\...
1
vote
2answers
61 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
100 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 Vi)...
5
votes
1answer
78 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
104 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
61 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
65 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 / n$....