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
2 views

how to solve recurrence T(n) = 2T(n/2)+n using substitution method

The required solution is given. I have to prove that it's solution is O(nlogn). My idea is shown below: I have to prove, T(n) <= cnlogn for some constant c T(n) <= 2clog(n/2) + n = ...
1
vote
2answers
79 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 ...
0
votes
0answers
36 views

Can any program be represented through graph theory?

So my understanding is that each variable in a program could be represented as a node which feeds into other nodes which use the variable nodes to produce a result (functions). And you can define the ...
3
votes
0answers
26 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
34 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
1answer
81 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
47 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
86 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
59 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
91 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 ...
-3
votes
0answers
25 views

Why does the formula hold?

I am looking at the proof that the randomized quick-select algorithm runs in expected $O(n)$ time. Could you explain me why the formula $t(n) \leq bn \cdot g(n)+t \left( \frac{3n}{4} \right)$ ...
1
vote
0answers
34 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 ...
0
votes
1answer
47 views

Amortized analysis of binary counter with increment and resetting operations

I have a question about http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Amortized/accounting.htm and to be specific the variant with Reset operation. First, 9th line of increment sets ...
1
vote
1answer
27 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
75 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
45 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
17 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
23 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
35 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
59 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
31 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
53 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
302 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
72 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
38 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
35 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
56 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
38 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 ...
1
vote
1answer
52 views

Knapsack Greedy Approximation: Worst Case

I am currently studying approximation algorithms and I have run into an issue with a study problem. The approximation algorithm is for the general Knapsack problem, and it proposes a greedy approach, ...
0
votes
0answers
22 views

Proving that a simple algorithm is $\Omega(n^2)$ for all inputs [duplicate]

I am given the following algorithm, which checks whether a given matrix is symmetric: ...
1
vote
2answers
88 views

Reachability matrix in time $O(|V| \cdot |E|)$

Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a ...
2
votes
1answer
40 views

Simplifying a nested sum

I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big ...
0
votes
0answers
14 views

Runtime of this loop [duplicate]

I need some advice on how to determine the runtime of this loop : s=0 for ( i=1 , i <= 2^m ; i=i*2 ) { s++ } return s With $C_1$ = actions ...
0
votes
0answers
193 views

Best- and worst case for Mergesort using Bubblesort for small lists

Problem statement: Merge sort is so modified that for array sizes below 11, instead of recursive Merge sort, the array is sorted using Bubble sort. Will there be any good and bad cases now? Give ...
-1
votes
1answer
36 views

What is the time complexity (big O) of this nested for-loop? [duplicate]

What is the time complexity (big O) of this nested for-loop? I believe it's either O(n) or O(n^2) ...
0
votes
0answers
36 views

Fat partitioning (by Bentley McIlroy 3-way partitioning Quicksort Algorithm)

What is fat partitioning (used by Bentley McIlroy 3-way partitioning) and how does it perform better than the partitioning mechanism in Tony Hoare's original Quicksort, in terms of memory usage, ...
0
votes
1answer
47 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
4
votes
3answers
80 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: ...
1
vote
0answers
53 views

Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively. Assume that you have to ...
2
votes
1answer
27 views

About having analytic control over any algorithm which finds perfect matchings.

A trivial algorithm to decompose a degree-d (n,n)-bipartite graph into d disjoint perfect matchings is this : direct all the edges from left to right and put capacity one on each of them - then add a ...
0
votes
1answer
38 views

Running time of recursive algorithm with geometric series

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
0answers
15 views

Running time of recursive algorithm [duplicate]

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
1
vote
2answers
65 views

Are hardware specs relevant in software performance comparisons?

I notice occasionally in blogs or articles comparing different languages, algorithms, etc. that the author will divulge info about the processor used in the testing. Is this meaningful? Shouldn't ...