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
0answers
37 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
16 views

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

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

Sub-Array with a unique element [on hold]

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
17 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
29 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
39 views

algorithms, number of instructions in the code [duplicate]

How many instructions as a function of the input size N? ...
1
vote
2answers
33 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
36 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
30 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
29 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. ...
-3
votes
0answers
36 views

Analysis of algorithms - comparing runtime in 2 computers

Suppose that Computer A takes 1 minute to run an algorithm, when input length is 100. Computer B is twice as fast, and I need to know what's the maximum size of the input it can handle in 1 minute. ...
1
vote
2answers
49 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
242 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
71 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
29 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
34 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
55 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
45 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
36 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
32 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
80 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
34 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
128 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
28 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
23 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
37 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
76 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
52 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
26 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
31 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
63 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 ...
-1
votes
2answers
56 views

Is there any other way of getting a function from this piece of code?

I have this pseudocode function mysterious(N): count = 0 for i = 0 to N: if (i mod 3 == 0): count = count + i return count The ...
1
vote
0answers
19 views

Why does response time increase with throughput? [closed]

I'm seeing this pattern that the response time increases as throughput increases, and that the throughput has a peak after the response time starts rising. This seems counter-intuitive. It seems like ...
4
votes
1answer
113 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
1
vote
0answers
42 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
-2
votes
1answer
71 views

What is the algorithm to add 2 binary numbers with boolean operations?

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
1
vote
1answer
26 views

Splitting permutations into transpositions

Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$. Otherwise we interpret ...
1
vote
1answer
66 views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
-4
votes
2answers
89 views

How long would it take a computer with twice the processing power to solve a polynomial time problem?

Say I have some problem of $O\left(n^k\right)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x'$, which has double the computing ...
4
votes
1answer
70 views

Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
0
votes
1answer
94 views

Why is Comb-sort (aka Dobosiewicz-sort) faster than Cocktail-sort (aka shake-sort)?

According to wikipedia, Cocktail-sort has an average performance of $O(n^2)$, whereas Comb-sort's average performance is $Ω(n^2/2^p)$, where $p$ is the number of increments. There's no explanation ...
2
votes
3answers
245 views

Analysis of very simple algorithm [duplicate]

I need to find the time complexity of the following simple algorithm. Calculate the time complexity of the following algorithm: ...
1
vote
1answer
230 views

I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf ...
5
votes
1answer
280 views

Checking whether all integers appear exactly once

Let $\texttt{a[]}$ be a finite array. We want to check whether every number between $\texttt {min(a[])}$ and $\texttt {max(a[])}$ appears exactly once. An obvious solution is sorting the array in ...
0
votes
0answers
45 views

Analyzing the time and space requirements of a Most Significant Digit first radix sort algorithm

In a previous question of mine, I asked how efficient is the Least Significant Digit first radix sort algorithm for sorting 32-bit integers. It turns out that the bounds are: Time: $ \Theta ...
5
votes
1answer
1k views

Is radix sort really O(n) for sorting 32 bit integers?

I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first. $k$ is the ...