New answers tagged runtime-analysis
3
There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.
0
Let me add one possible way of solution. By $T$ we denote the number of max updatings.
Direct analysis of cases after using mathematical induction gives
$$T(n) = n \cdot T(n-1) + (n-1)!$$
and from here obtain expected value
$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{i=1}^{n}\frac{1}{i} - 1 =\\
= \...
1
You are right about the running time of the second algorithm, i.e., Shuffle1$(A)$. Its running time is indeed $O(n^{3} \cdot m^2)$.
To analyze the running time of the first algorithm, i.e., Shuffle$(A)$, you can formulate the recurrence relation as follows:
$$T(n) = 4 \cdot T(n/2) + O(n^2)$$
Note that, Random(10) takes time $O(10^2) = O(1)$.
You can indeed ...
2
If the maximum element is the $n$'th, then $\text{maxNum}$ is not necessarily updated n times. Consider for example the case where the second largest element is in first position. Then $\text{maxNum}$ is updated twice no matter where the largest element is.
Let $U_n$ be the average number of updates of $\text{maxNum}$ for a list of size $n$. Let $i_\max$ ...
2
Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution for $Pr(t_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the location the maximum in the array.
...
1
Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.
An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n_0$ and some constant $c>0$ such that for every $n \ge n_0$, $f(n) \le c n^2$.
Moreover, given some other function $g(n) = o(n^2)$ ...
0
If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprint in arxiv discussing this. We got a simpler sum and a tighter constant, but you need to have some idea about potentials.
Essentially we treat the array as a forest of heaps and define the potential to be the sum of the ...
Top 50 recent answers are included
