People who code: we want your input. Take the Survey
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