People who code: we want your input. Take the Survey

# Tag Info

## Hot answers tagged algorithm-analysis

3

Here is a way to show it without limits. Let $n = 2^x$. Now you are comparing the growth rates of $2^x$ and $x^x$.

3

$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$ Denote the support of $f$ by $f_1\le f_2\le...\le f_s$. Given a frequency sequence $f$, denote by $E_{f,a}$ the random variable $\hat{f}_a$ where the stream frequencies are given by $f$ (the evaluation depends on the inner randomness of the sketch and the input stream). The probability that the hash of one ...

2

The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments. Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as $$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log_3{2})^2.(\log_3n)^2$$ However, this modification will only bring a ...

1

Here is a simple reasoning that shows your greedy algorithm is correct. No mathematical induction is required. Call an image critical if the greedy algorithm places a guard $0.5$ after it. The algorithm ensures that each critical image is more than $1.5$ away from the previous critical image (except the first image, before which there is no image). That ...

1

Let me split the answer to three parts, so it will hopefully clear all misundestandings you have on the concepts. What are big-O and big-$\Omega$? Big-O and big-$\Omega$ are two mqthematical properties of functions over natural numvers. Their formal definition state that: $f=O(g)\iff \exists c>0:\forall n: f(n)\le c\cdot g(n)$ $f=\Omega(g) \iff \exists ... 1 Consider$f(n) = n^2$. Then we have$f(n) \in \Omega(n)$but not$f(n) \in O(n)$. However, as you stated it, it is better to give a tight bound for best and worst cases, with the$\Theta$-notation, because saying "the worst case is exactly$n^2$operations" is a better information than "the worst case is at least$n$operations". 1 We can describe quicksort with a random pivot as follows. Assume for simplicity that$S_{(i)} = i$. First, choose a permutation of$\{1,\ldots,n\}$. Then, whenever processing some subarray, choose the element that appears first in the permutation as the pivot. Suppose we are interested in the number of elements compared to$i$. Suppose that$i$is found at ... 1 This is not the answer to your question, but maybe you can use some elements of it. For$i<j$, let us denote$X_{ij}$the random variable: $$X_{ij} = \left\{\begin{array}{rl}1 & \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$ and$A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}\$. Since a comparison ...

Only top voted, non community-wiki answers of a minimum length are eligible