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

2
votes
1answer
24 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
16 views

optimal minimum set cover problem [on hold]

I am implementing optimal set cover problem but I am facing problem. Can anyone help me regarding optimal algorithms related minimum set cover problem such as Linear programming, Primal dual, brute ...
0
votes
0answers
29 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
47 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
24 views

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

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
32 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
23 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
64 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
33 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
50 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
27 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
15 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
31 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
74 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
49 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 ...
0
votes
1answer
17 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
22 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
14 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
59 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
53 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
14 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
104 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
votes
0answers
24 views

How do I prove that 1 function is an upper bound of the other? [duplicate]

If for every $n > 0$ and some $b > 1$, $T(n) \le h(n)$ and $h(n) = O(h(n/b))$ then how can I prove that $T(n) = O(h(n))$, I understand that $T$ is bounded by $h$, so $h$ must be its upper bound, ...
1
vote
0answers
37 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
65 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
23 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
52 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
85 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
57 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
62 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
230 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
189 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
279 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
40 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 ...
0
votes
2answers
41 views

Is the Wall-Follower Algorithm in P?

Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)? In particular, are there poly time algorithms for solving the Perfect Maze problems? A perfect maze has the following ...
0
votes
1answer
68 views

How do we derive the runtime cost of Karatsuba's algorithm?

I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it. I seem to have gotten about 75% of the way to the solution on my own, but ...
2
votes
1answer
31 views

Residence time in multi server system

I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is: ...
0
votes
0answers
16 views

Confusion with space and time usage [duplicate]

The following is my own set-up code: ...
1
vote
2answers
54 views

Cost of shifting a number

I was wondering what would be a time complexity of shifting a binary or a decimal number? For example: 0011, when I shift it left I get 0001. I was thinking that the time complexity is $\Theta(n)$, ...
0
votes
0answers
20 views

Runtime and space usage of a snippet of code [duplicate]

I've been trying to understand time complexity and space complexity by writing my own snippets of code and solving them. Can you see if I'm correct? ...
0
votes
0answers
27 views

Asymptotic analysis of shifting/multiplying

I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this line "return (X * B^ (2 * m)) + ((Z) * B ^ (m)) + (Y)" where X,Z,Y are ...
3
votes
2answers
95 views

Why does quicksort work well with virtual memory?

Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is ...
0
votes
1answer
31 views

Prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values

How can I prove that a stable algorithm cannot solve an ill-conditioned problem with a precision greater than that of input values ? It seems obvious to me, since an ill-conditioned problem is that ...
1
vote
1answer
22 views

Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
2
votes
1answer
47 views

Kosaraju's algorithm's time complexity

I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that using an adjacency list representation gives a time complexity of ...
1
vote
1answer
30 views

Efficient computation of Kronecker product

Given matrices $A \in \mathbb{C}^{n_1,m_1}, B \in \mathbb{C}^{n_2,m_2}$ a naive way to computer the Kronecker product would be as such: $M = \operatorname{zeros}(n_1n_2,m_1m_2)$ (initialize an empty ...
1
vote
1answer
44 views

Expected number of random interval flips needed for sorting a random array

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort. Assume that $A$ is an array initialized by a random ...