8
votes
1answer
76 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
0
votes
0answers
40 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
0
votes
1answer
60 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
2
votes
1answer
98 views

A question about sorting

I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
0
votes
1answer
77 views

How do I estimate the time taken? (Growth Rates)

Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size ...
2
votes
0answers
66 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
0
votes
2answers
167 views

Complexity of sorting algorthms

I've read an article (German) about different sorting algorithms where the author states this: [Smoothsort] is a sorting algorithm that uses swaps to sort and does not need any extra external ...
2
votes
2answers
375 views

Time complexity of sorting a partially sorted list

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order. How would you sort the whole list given the following: a) $f(n)=O(1)$ b) $f(n)=O(\log n)$ c) $f(n)=O(n^{1/2})$ d) ...