New answers tagged

2

If i understand you correctly, then the following holds: $\sum_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$ Thus there is no asymptotic gain.


1

First of, you can make some of the bounds a little tighter and replace some $E$s with $V$s. The while loop at the beginning will only run $O(|V|)$ iterations (you visit every node only once), and the for (Edge edge : graph.adj(min)) loop will run only $O(|V|)$ iterations at most (a node can have at most $O(|V|)$ adjacent edges). Same with the log factors, ...


0

Your analysis is correct, but not tight. Instead of considering the while loop and the for loop separately, it is better to consider them together. The inner body of the for loop runs once for each (vertex,pair) edge, for a total of $2|E|$ times. Therefore the total running time of all relax operations is only $O(|E|\log |E|$). The total running time of ...


1

Look at how many steps the inner loop is taking. It's $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. However the geometric series tells us: $$\sum_{k=0}^{\lceil\log n\rceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2^k} = 2n$$


1

After a bit more thinking, I realised it's actually doable in $O(n)$ If you normalise your hypercube onto the origin then to find the face the point lies on you simply need to find the axis of the point with the largest magnitude. So, if the point is at $(0.2, 0.4, 0.7, 0.5)$, the point will be closest to the face facing in the positive z direction.


1

Your formulation of $f(n) \neq o(g(n))$ is wrong. Recall that $f(n) = o(g(n))$ if for all $c > 0$ there exists $n_0$ such that for all $n \geq n_0$, we have $f(n) \leq cg(n)$. The negation of this is: there exists $c > 0$ such that for all $n_0$ there exists $n \geq n_0$ such that $f(n) > cg(n)$. Take $c = 1$. Given $n_0$, let $n = \max(n_0,10^{...


0

start like this $n \ge 10^{10}$, $\forall n \ge10^{10}$ raising exponent n on both side of inequality, we get $\implies n^n\ge10^{10n}, \forall n \ge10^{10}$ $\implies 10^{10n}\le n^n,\forall n\ge 10^{10}$ $\implies 10^{10n}=O(n^n)$ $\implies n^n \notin o(10^{10n})$ Here the $c=1$ and $n_0=10^{10}$ The value of $c$ and $n_0$ must come from the derivation.


1

One possibility is to merely apply the definition. That is, we see that if $\lim_{n \to \infty} f(n) / g(n) = 0$, then $f(n) = o(g(n))$. Computing this, we have that $$\lim_{n \to \infty} f(n) / g(n) = \lim_{n \to \infty} n^n/10^{10n} = \infty \neq 0.$$ We conclude that $f(n) = o(g(n))$ does not hold.


3

Suppose for simplicity that $m=2^a$, $n = 2^b$, $c_0=1$, $c_1=0$, and the base cases are $T(1,\cdot) = T(\cdot,1) = 0$. Then $$ T(2^a,2^b) = 2T(2^{a-1},2^{b-1}) + b = 4T(2^{a-2},2^{b-2}) + b + 2(b-1) = \cdots $$ The number of summands is $c = \min(a,b)$, and using this notation we obtain \begin{align} T(2^a,2^b) &= b + 2(b-1) + 4(b-2) + \cdots + 2^{c-1}(...


1

It is possible. Example $g_A(n)=1$, $g_B(n)=2$, and $f(n)=1$. It is also necessary, since $g_B(n) = 2 g_A(n) \in\Omega(f(n))$. To see that $ 2 g_A(n) \in\Omega(f(n))$ you can use the definition of $\Omega(\cdot)$. From $g_A(n) = \Omega(f(n))$ you know that here is some $n_0$ and some $c>0$ such that, $\forall n \ge n_0$, $g_A(n) \ge c f(n)$. This ...


3

Recall that the sum of $\log$'s is equivalent to the $\log$ of products. That is: $$\log(xy) = \log x + \log y$$ Thus we can change your function: $$ \begin{align} \sum_{i=n}^{n+m} \log i &= \log \prod_{i = n}^{n + m} i\\ &= \log (n \cdot (n+1) \cdot (n+2) \cdot \ldots \cdot (m-1) \cdot m )\\ &= \log (m!\ /\ (n-1)! )\\ \end{align} $$ Then we ...


2

O((m +1) log(n+m)). It’s obviously an upper bound. But also most values have a logarithm close to the maximum, so it’s also a good lower bound. In your particularly simple case, the Stirling formula will give you a better result, but you asked for big-O only.


2

The answer depends on what you mean exactly by "an algorithm has a big-theta notation". Asymptotic notations is used to denote set of functions, not algorithms. It is important to know what function you are talking about. If given an algorithm $Alg$, you denote by $f_{Alg}(n)$ the maximum running time of $Alg$ among all inputs of size $n$, your statement is ...


0

Forget about the outer loop. Just remember that on it's way from $N$ to 1, $i$ gets divided by $2$ on each iteration. Now, on the first iteration of the second loop, $j$ will go from $0$ to $N$, and so we will have $N-0+1 = N+1$ steps. On the second iteration, $j$ will go from $0$ to $\frac N2$, so we will have $\frac N2 + 1$ iterations. You can see how ...


0

When the value of i is N, the inner loop will run N times Then, the value of i becomes N/2, so the inner loop will run N/2 times then, the value of i becomes (N/2)/2, so the inner loop will run N/4 times This continues till the value of i becomes 1, so the total time complexity is : $$N + N/2 + N/4 + N/8 + ....... + 1$$ Or $$1 + 2 + 4 + 8 + 16 + ..... N/...


0

A more practical approach: The most executed statements in this example is the ones inside the innermost loop, for example count = count + 1 This statement counts how many times it is executed, which means that the total runtime is approximately proportional to the output. So, try to run this program with various inputs and see what the output is. I ...


3

The runtime for this algorithm is $\Theta(n)$. By rewriting the iterative formula as a recurrence relation $T(n)=T\left(\frac{n}{2}\right) + n$ we can use Master Theorem to analyze the runtime. The recursive equation doesn't meet the criteria for the first or second cases but it does meet those for the third, meaning $T(n)=\Theta(f(n))$ where $f(n)$ is the ...


4

The second for-loop while be executed N + N/2 + N/4 +....+ N/N , the first for-loop decides how much the second for-loop will be executed. When i = 0, j loops until N , i = N/2, j loops until N/2 , And so on , The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)


1

there is two loops .. the inner loop over O(N) numbers(0 to i at most i=N) and the outer one starts the loop from N and slice it by two in each iteration (N -> N/2 -> N/4 ..) therefore the big-O of the algorithm is O(Log(N)*N).


1

*Cough* Nice homew... Ahem It's O(N*log(N)) because the outer loop runs log(N) times (i from N to 1, dividing by 2 each time) and the inner loop runs i times (so N times the first time for example, then less).


0

This requires some basic logarithm concepts. You may have come across logarithmic equations with general definition as: logb(x) = y is valid if by = x | Here b is the base, y is the exponent value that makes by = x Let's consider x having a value 64. Below are some logarithmic outputs (y) with different bases: log2(64) = 6 | As, 64 = 26 (base 2) ...


0

Polynomials of higher degree grow faster than polynomials of lower degree. The polynomial with the n + n^4 is of degree 4. The polynomial with the n^2 + n^3 is of degree 3. Therefore, the n^4 polynomial grows faster than the other polynomial.


1

Vertex Cover is fixed-parameter tractable. There is a simple $2^k n$ algorithm to find a VC of size $k$. This should beat the naive algorithm. The current state of the art is something like $1.24^k n$. Under some assumptions there is no algorithm for k clique with running time $f(k) n^c$. If your graph has some special structure the results can be ...


2

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials. Plotting the curves is not so helpful, since these are asymptotic statements. That said, if you're interested in particular $V$ and $k$, then your best option is to empirically check which of ...


1

If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$. Now I guess the m-th ugly number is greater than $2^{m^{1/3}}$, so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time. ...


0

Yes, asymptotically. You can see that $n + n^4 = \omega(n^3 + n^2)$ by taking the limit: $$ \lim_{n \to \infty} \frac{n^4 +n}{n^3 + n^2} = \lim_{n \to \infty}\frac{n + n^{-2}}{1 + n^{-1}} = + \infty $$. See also this answer.


Top 50 recent answers are included