New answers tagged

2

It is easy to show that $\prod_{i = 1}^{n}x_i$ is maximized when all $x_i$'s are equal, i.e., $x_i = n/k$ for every $i \in \{1,\dotsc,k\}$. Therefore, $$\sum_{i = 1}^{k} \log x_i = \log \left( \prod_{i = 1}^{k} x_i \right) \leq \log \left( \prod_{i = 1}^{k} \frac{n}{k} \right) = k \log (n/k) \leq n = O(n)$$ Thanks to @JohnL. for pointing out that $k\log_{e}(...


1

Although $\mathcal O(f(n))$ will often be given as a function, e.g. $\mathcal n^2+n=\mathcal O(n^2)$, strictly speaking $\mathcal O(f(n))$ is a set of functions, so the precise statement is $n^2+n \in \mathcal O(n^2)$. The expressions $\mathcal \log(O(f(n))$ and $\mathcal O(f(n))^2$ don't really make sense. You can't do math on $\mathcal O(f(n))$, other ...


8

In order for $f(O(n)) \in O(f(n))$ to hold you essentially want $f$ to satisfy $f(cn) \le df(n)$ where $n$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $c$, while $d$ is a constant that can be chosen as a function of $c$ (but not as a function of $n$). For example $\log cn \le \log c + \log n \le (1+ \log c) \log ...


14

To prove or disprove this kind of equality with $\mathcal{O}$, you need to go back to the definition of $\mathcal{O}$ with inequalities. For example, let's study the question $\log(\mathcal{O}(n)) = \mathcal{O}(\log n)$: $f\in \log(\mathcal{O}(n))$ means that there exists a function $g\in\mathcal{O}(n)$ so that $f = \log g$. That means there exists a ...


0

Because the work done is $$ T(n) = 2T(n/2) + n^2 \leq \sum_{i=0}^{\log_2 n} 2^i \left(\frac{n}{2^i}\right)^2 = n^2 \sum_{i=0}^{\log_2 n} \frac{2^i}{2^{2i}} = O(n^2). $$ Try for yourself to see what happens when you remove the factor squared in the summation.


0

The running time (and how it changes) of any algorithm implementation will vary across platforms (hardware, operating system, compiler etc) and the input data. So it looks hard to find a simple relation for the array size up to which insertion sort will perform better than quick sort (and that too for all inputs). Perhaps what we can do is assume the ...


1

why do we say the inner loop's upper bound is $2^i$? The outer sum (sigma) is going backwards, so to speak. The first iteration of the sigma makes the inner summation from $j=1$ to $j=1$, whereas, in fact, it should be from $j=1$ to $j=16$ (in your case). In each iteration of the outer loop, we are doubling the variable $k$ from the outer for-loop (recall ...


2

Your intuition tells you correctly that it should suffice to check the bound for the term $3n^2+2$, since $3n^2+2$ dominates the function $4n+1$. nir shahar has pointed that out in their answer. However, for a formal proof that $f(n) = \mathcal{O}(n)$, you will need to formalize your intuition that $3n^2+2$ dominates $4n+1$ and you will also have to argue ...


Top 50 recent answers are included