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
1answer
59 views

Good mathematical book on algorithms

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 ...
0
votes
1answer
40 views

Merge two series of sorted number, one much longer than the other

This is the problem: Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons. I have come up ...
0
votes
1answer
33 views

approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality

I have the following question for the travelling salesman problem: The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph G. Instead of the traingle inequality, ...
5
votes
2answers
75 views

How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
1
vote
1answer
55 views

Analysing Space Complexity

I have to compute the space complexity of this function: ...
2
votes
1answer
55 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly p points. We also (randomly) place c circle centres. I'm trying to find an algorithm that will allow ...
0
votes
2answers
37 views

Running time analysis of a linear algorithm seems to me quadratic

I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I ...
0
votes
1answer
66 views

Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural ...
2
votes
2answers
57 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: ...
2
votes
1answer
74 views

How can I compute the time complexity of this image processing algorithm?

Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing. I simplified the algorithm ... so that we focus only on the problematic part. ...
2
votes
0answers
29 views

How to understand the formal analysis of quickselect?

According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof ...
3
votes
0answers
19 views

Running time for threshold function evaluation?

A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows: $$f(x_1, ...
5
votes
4answers
85 views

Calculating the number of multiplications necessary to evaluate a polynomial

I was watching a lecture and got confused over a slide. This is what it says: Consider a polynomial - first representation $$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$ The ...
1
vote
2answers
18 views

Number of operations performed in increment operators [closed]

How many operations are performed in the following in order to get a running time function of an algorithm: x = x + 1 x += 1 ...
3
votes
1answer
33 views

Running time function for an algorithm with while and for loop

I have trouble determining the running time function for algorithm below. I know that there are initially two assignment operations, int i=n and ...
5
votes
1answer
71 views

How does Knuth measure the running time of this program?

I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand ...
1
vote
1answer
25 views

How to test image segmentation algorithms? [closed]

What would be an ideal environment/manner to judge the effectiveness of multiple segmentation algorithms? The goal is to determine which algorithms provide the best results for pre-clinical imaging. ...
1
vote
1answer
22 views

Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
1
vote
2answers
85 views

Exercise on Divide&Conquer's technique

I need help on this exercise: You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all ...
3
votes
0answers
31 views

Alpha beta algorithm with Iterative Deepening analysis

I'm implementing a chess engine. Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster ...
1
vote
0answers
44 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
1answer
87 views

How can I prove algorithm correctness? [closed]

How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the ...
4
votes
1answer
53 views

Period of a pseudo-random sequence generated using an LFSR

I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR). I have read from many sources that the length of the pseudo random sequence generated ...
2
votes
3answers
95 views

Algorithm for finding all the combinations on a boolean array

I have to design an algorithm to do the next task: I have one array of booleans. For example: Array: [0 1 0 0 1 0 1 1] I want to obtain all the existing combinations of 1's, having in mind that ...
0
votes
1answer
65 views

Finding median weights in all paths of an AVL tree with weighted nodes

I need some help with proving the complexity of the following problem (I'm new here, so please excuse my "newbie-ness") Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree ...
1
vote
1answer
94 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
1
vote
0answers
36 views

Why does the firefly algorithm need an intensity function?

I am studying the firefly algorithm and I would like to ask about the Intensity function that is defined at the beginning of the algorithm. What is it for? Some literature give different functions ...
1
vote
1answer
54 views

Amortized analysis of binary counter with increment and resetting operations

I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation. First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ because ...
1
vote
1answer
29 views

Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
2
votes
3answers
77 views

What is more important in an algorithm, small runtime or small memory usage?

I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same ...
0
votes
1answer
34 views

Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

I am trying to solve the following question There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose there's another computer which is 10 times faster. How much bigger can our $n$ ...
3
votes
0answers
47 views

Approximation ratio of a greedy grid-cover algorithm

We're given a $N\times M$ grid, and we want to cover all coordinates in the greedy by rectangles of size $\le k$. Consider the following greedy algorithm. At each iteration, it chooses a rectangle ...
1
vote
0answers
18 views

How do I apply a single iteration of Floyd's algorithm to an adjacency matrix? [closed]

I have the following adjacency matrix for a graph with nodes {a,b,c,d}: \begin{bmatrix} & & a& b& c& d\\ & & & & & \\ a& & 0& ...
0
votes
1answer
26 views

Sub-Array with a unique element [closed]

You have an Array of length n. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive ...
-2
votes
1answer
34 views

It is possible to implement insertion sort for sorting linked list ?

it is possible to implement insertion sort for sorting linked lists ? will it have the same O(n^2) efficiency as the array version ?
0
votes
0answers
31 views

a way to get shortest path tree

Given the shortest path tree of a directed graph $G=(V,E)$ and $w\colon E\to R$, source vertex $s$ and an assumption that there are no negative cycles in the graph. In the homework assignment we need ...
0
votes
2answers
41 views

algorithms, number of instructions in the code [duplicate]

How many instructions as a function of the input size N? ...
1
vote
2answers
37 views

Time complexity of a classical version of Shor's algorithm

I'm sorry if this question seems too naive. I've read the Shor's algorithm of factoring big number using quantum computer on Wikipedia. It says,the key step is to find the cycle of the function ...
0
votes
0answers
66 views

Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
1
vote
1answer
31 views

Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case

This is a question from Introduction to Algorithms by CLRS (Exercise 9-1-1). The approach I thought of is compare the first two numbers, assign the lower number min and the bigger one to next_min ...
3
votes
0answers
32 views

Is there a known worst start configuration for Ford-Johnson sorting algorithm?

By this I mean a permutation of the $n$ input items to be sorted such that the number of comparisons taken to produce the correct order is maximal over all of the possible permutations of $n$ items. ...
1
vote
2answers
55 views

Complexity of an algorithm

I tried to solve the following exercise : What is the order of growth of the worst case running time of the following code fragment as a function of N? ...
8
votes
2answers
370 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 ...
0
votes
1answer
21 views

Transitions needed for dividing two fixed integers

Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively. A transition is an element of $Q \times \Sigma ...
1
vote
0answers
76 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
2
votes
1answer
39 views

Correctness proof for finding weighted maximum independent set for a tree

The maximum weighted independent set for a tree can found out using the following dynamic programming approach. Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } ...
0
votes
0answers
36 views

Calculate the computational complexity of multiplication AxAT

I need to implement an algorithm that calculates the symmetric matrix obtained by performing AXAt being At the transpose of A. I did my analysis from two perspectives: (1) The first thing I notice ...
4
votes
1answer
56 views

Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that: For any $\epsilon >0$, there are probabilities for which the ...
1
vote
0answers
57 views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
2
votes
2answers
40 views

Understanding an upper bound in the analysis of Karger's algorithm

I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have. Here, under the section about finding all min cuts, they have ...