New answers tagged

4

No. Consider, for instance, $$T(n,m) = \begin{cases} m, & \text{$m$ even} \\ \frac{m}{n}, & \text{$m$ odd} \end{cases}$$ and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' > 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since ...


0

We know that if the limit $$\lim_{n->\infty}\frac{f(n)}{g(n)}$$ exists and is strictly between zero and infinity, then $f(n)\in\Theta(g)$. In this case, we need to evaluate the limit $$\lim_{n->\infty}\frac{a_k n^k+a_{k-1}n^{k-1}+\cdots+a_1 n+a_0}{n^k}.$$ But this limit can be split into the $k+1$ limits $$\lim_{n->\infty}\frac{a_i n^i}{n^k},$$ ...


3

First, $|V|$ is the number of vertices and $|E|$ is the number of edges. The point is that if a graph is connected it must have at least $|V|-1$ edges. Therefore, $|V|\leq |E|+1$, so $$|V|\log|V| + |E|\log|V| \leq 2(|E|+1)\log|V|\leq 3|E|\log |V|\,.$$ Writing $|V|=O(|E|)$ is something of an abuse of notation. $O(\cdot)$ is an asymptotic statement about ...


0

Let me focus on the following question: Is $3^nn$ a tight bound on $\binom{n}{k}n2^{n-k}$? First, let us see that this is a valid bound. This follows from the binomial theorem: $$ \sum_{k=0}^n \binom{n}{k} n 2^{n-k} = 3^nn. $$ Since there are $n+1$ summands in the expression, we deduce that $$ \max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} \ge \frac{3^nn}...


1

In simple terms, $T(n)$ is the running time or time complexity of an algorithm. while $F(n)$ can be thought of as speed bound. $F(n)$ can be: constant: $F(n) = c$ Linear: $F(n) = a n + c$ Quadratic: $F(n) = a n^2 + b n + c$ Cubic: $F(n) = a n^3 + b n^2 + c n + d$ Logarithmic, exponential,... etc. F(n) takes an input of size n, and tell us how much time ...


1

T(n) is a function that has been conceived in a effort to describe the behavior of a program. There are many other possibilities, but that should be the case, in the context of computer science. That doesn't mean we will actually write T(n) down, because i) it can be too complicated, and ii) it is probably not essential to do so. Then comes f(n), which is ...


1

This is not possible. If this is the case then we could extract a sorted list in linear time; $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $\Omega(n \log n)$ lower bound worst case, so this is not possible.


2

The value of $i$ at the $k$'th iteration (starting from zero) is $i_k := 2^k$. The inner loop runs $i_k$ times, for a total of $i_0 + i_1 + \cdots + i_K$, where $K$ is the largest number such that $i_K \leq n$, that is $\lfloor \log_2 n \rfloor$. Therefore the running time is $$ \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k = 2^{\lfloor \log_2 n \rfloor + 1} - 1 ...


Top 50 recent answers are included