All Questions
11
questions
2
votes
1
answer
182
views
Sit N people around a table so as to minimize the maximum difference in height between any two adjacent people
(This is actually a coding challenge for an interview. Unfortunately, only 2 test cases are coded, so even if my solution passes them both, that doesn't tell me I've found the correct solution. Also, ...
- 315
1
vote
2
answers
7k
views
How many comparisons does the insertion sort use to sort the lists in question
I have two lists to sort using insertion sort:
How many comparisons does the insertion sort use to sort the list
$n, n − 1, . . . , 2, 1$?
How many comparisons does the insertion sort use to sort ...
- 1,189
3
votes
1
answer
1k
views
Sort an array given the number of inversions
Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
- 31
1
vote
1
answer
121
views
Run Time Analysis of the Merging Part in Mergesort
I want to show that if I apply the Mergesort on a set $M$ with $n$ elements and divide $M$ in $2<b\le n$ parts instead of just $2$, that the I need $O(nlog_2 (b))$ time for the merging part.
So ...
- 297
1
vote
1
answer
94
views
Is there a typo in this runtime analysis of selection sort?
This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6.
The instructor is doing a runtime analysis of selection sort. Here is ...
- 1,884
3
votes
1
answer
856
views
Expected time of Quicksort
I am reading the proof of the theorem:
The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time.
The proof is this:
For simplicity in the timing analysis assume ...
user175343
3
votes
2
answers
1k
views
Find both the largest and second largest elements from a set
Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons.
Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient.
...
- 14k
4
votes
1
answer
3k
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 ...
- 44
2
votes
1
answer
181
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 ...
- 1,511
0
votes
1
answer
127
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 $...
- 171
3
votes
2
answers
992
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) ...
- 31