Tag Info

New answers tagged

1

The second algorithm uses less space, but the first does fewer comparisons in general. In both algorithms you compare every node with alphabetically with the target until you find one that’s greater. In the second you also test each of those nodes except the last to see whether it has the desired property; in the first, however, you test only those back to ...


1

The "known" subset-sum problem takes as input a list L of n integers and a target sum A. Partition L into n lists (each containing one of the n integers). Append a zero to each of the n lists. Now, each list contains an integer from L and a $0$. Now, feed the n lists and the target A into an algorithm that solves your problem. If your algorithm solves ...


0

It is just simpler to describe the situation with a single input tape -- in particular, if you want to compare the power or efficiency of machines with differing number of tapes, it is convenient that the format of the inputs to all the machines are the same. But it is not a particularly deep choice -- if you have input on one tape and want it spread across ...


0

Too long for a comment: When multiplying in bases other than $2$ you have two different sorts of carries. In base $2$, each individual bit multiplication cannot carry. The only carries you get are when you add the bit multiplications together. In other bases you can get carries in the multiplication step. In base $10$, for example, when multiplying $79 ...


1

An important part of these gadget schemes is that there is a 3-clique somewhere called the palette that arbitrates the logic roles of colors. In other words, there are 3 nodes all connected to each other, labeled $v_T$, $v_F$, and $v_R$. The palette can be arbitrarily colored, and whatever colors are chosen represent the 3 logic values. Then when a ...


0

You'll have to seperate each case n odd, n even. If n is even, define: $ U_p = T_{2p} = T_n $ You get : $ U_p = 2U_{p-1} + 3 $ Dividing by $2^p$ and setting $V_p = \frac{U_p}{2^p}$ you get: $ V_p = V_{p-1} + \frac{3}{2^p} $ Telescoping the $V_p$ you get : $ V_p -V_o = 3\sum_{k=1}^p \frac{1}{2^k} = \frac{3}{2}\frac{1-\frac{1}{2^p}}{1-\frac{1}{2}} = ...


0

I'm not really sure about this recurrence and the Hanoi tower, but an easy way to solve it is using difference equations: $$ T_{n-1} = 2 T_{n-3} + 3 $$ Now subtract this equation from the one in your question and denote $\Delta T_n = T_n - T_{n-1}$ and work your way to $\Delta T_1$. Then sum over $n$ and on LHS you'll have most terms cancelling out. Can you ...


0

I would suspect just mentioning a string and the pumping lemma is not a full proof that you found a string that cannot be pumped in any way. This is my try: The string $01^{p}2^{p}$ can be divided in three parts $x$, $y$ and $z$ only in these ways: 1) $x = \epsilon$, $y = 01^{a}$ $|$ $a \geq 0$ If x has length zero, y will always be a zero and some ...


0

Yes. Even better, there is a dynamical programming solution that uses $O(nk)$ steps.


1

Suppose $$ \Lambda = \pmatrix{\lambda_1\\&\lambda_2\\&&\ddots\\&&&\lambda_n} $$ Furthermore, suppose that $P$ is an orthogonal matrix, and that $U$ is the matrix consisting of the first $d$ columns of $P$. We then have $$ U^T\Lambda U[i,j] = \sum_{k=1}^n \lambda_k U[k,i] U[k,j] $$


1

Note that it is true (and interesting/useful) that $\mathcal{O}(n^c) > \mathcal{O}( Log(n))$ for $c>0$, so perhaps the sequence was meant to be: $\mathcal{O}(n^n) > \mathcal{O}(n!) > \mathcal{O}(b^n) > \mathcal{O}(n^c \cdot Log(n)) > \mathcal{O}(n^c) > \mathcal{O}( Log(n))$, for all $c>0$ and $b>1$.


1

$n^c$ is only bigger than $n\log n$ when $c>1$.


0

The last two elements should be swapped, as $n \log n$ grows faster than $\log n$. The other elements are ordered correctly.


2

$O(n\log n) > O(\log n)$. Otherwise, you're fine as far as I can tell.


0

Solve: $x^2 - 3x - 4 = 0 \Rightarrow (x-4)(x+1) = 0 \Rightarrow x = 4, -1 \Rightarrow T_n = A\cdot 4^n + B\cdot (-1)^n$. $T_0 = 0, T_1 = 1 \Rightarrow 0 = A+B, 1 = 4A-B \Rightarrow A = \dfrac{1}{5}, B = -\dfrac{1}{5} \Rightarrow T_n = \dfrac{4^n -(-1)^n}{5}$


0

It is the case that $$\frac{n^2 + n}{2} \leq 1\cdot n^2$$ as long as $n \geq 2$. So the answer is yes. Just remember that at the same time it's also of $O(n^3)$ and $O(2^n)$, since big-O only gives an upper bound. However, as a general rule, we want to find the smallest simple expression that works, and in this case it's $n^2$.


0

If you want to factor $X$, the input to your problem consists of the decimal representation of $X$, which consists of $n = \log_{10} X$ digits. Any division algorithms for an $k$-digit number by an $k/2$-digit number requires $\Omega(k)$ arithmetic operations on digits; the algorithm you suggest therefore takes $\Omega(\sqrt{X} n)$ time. That is, your ...


5

Actually, the classical NP-complete "vertex cover" problem is the decision problem: given natural number $k$ and graph $G$, is there a vertex cover of size $\le k$? If you could solve this problem in polynomial time, you could also find a cover of minimal size in polynomial time. The point is that given a vertex $v$, there is a vertex cover of size $k$ ...


1

All you want to show is that if $h\in \mathcal O(g)$ then $\tilde h$ defined by $$\tilde h(n) = f(n)\cdot h(n)$$ is an element of $\mathcal O(fg)$. The converse needs a case distinction for $f(n) \ne0$ and $f(n) = 0$ to go through.


1

Express combinations number via factorials, and then use Stirling's Approximation for factorials. Then you'll be able to prove what you want.


1

First, remember that the $\Omega$ notation gives a lower bound for the complexity, so if you have an implementation where every operation takes $cn$ time for some constant $c$, that complexity is $\Omega(\log n)$ too! Second, if you have a priority queue implementation that works under the given restrictions, you can use it to build a comparison sort ...


1

You correctly found that the j<n test in the second line is executed a total of $$\sum_{h=0}^m (n-5^h+1)$$ times, for some integer value of $m.$ This is almost the formula for the total number of iterations of the inner loop (the number of times the third line runs), which is $$\sum_{h=0}^m (n-5^h)$$ for the same value of $m.$ That's because the first ...


1

It is actually harder than that. It is #p-complete. For proof see this: http://www.math.washington.edu/~billey/colombia/references/valiant.permanent.1979pdf.pdf Also see these: http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete http://en.wikipedia.org/wiki/Computing_the_permanent


0

I would say that the run-time complexity of insertion sort is $\operatorname{O}(n^2)$, so you would take your $10$ times more data and square it.


2

Hint: Time complexity of Insertion sort is $O(n^2)$ Roughly speaking if $10^6$ records took $1$ second then $10\times 10^6$ records will take $10^2\times1=100$ seconds


0

Hint: what is the Time Complexity of insertion sort?


0

Suppose that you do not know the formula for the summation. But you do know the following: $$p(n) = \sum_{i=0}^n i^2\\ p(n+1) - p(n) = (n+1)^2 = O(n^2)\\ (n+1)^2 - n^2 = 2n + 1 = O(n)\\ 2(n+1)-1 - (2n - 1) = 2 = O(1)$$ This is only an intuitive approach; a more rigorous approach could make use of binomial forms and note that $p(n)$ must have a term ...


1

If your goal is only to find an approximate bound, there are several tricks: Let $s > 0$. Using the largest summand, we get $$ \sum_{k=1}^{n} k^{s} \leq n \cdot n^{s} = n^{s+1}.$$ To make the constant small, $$ \sum_{k=1}^{n} k^{s} \leq \sum_{k=1}^{n} \int_{k}^{k+1} x^{s} \, ds \leq \int_{0}^{n+1} x^{s} \, ds = \frac{(n+1)^{s+1}}{s+1}. $$ Indeed, this ...


2

Are you familiar with #P-complete problems? The prototypical example is: HC#: Given a graph $G$, how many Hamiltonian cycles does it have? Clearly, an efficient solution to HC# would immediately solve the NP-complete Hamiltonian Cycle (HC) problem, and by extension all NP-complete problems. On the other hand, it's not clear at all that an efficient ...


3

You might be interested in the answers to this related mathoverflow question, which gives several undecidable graph-theoretic problems. (Of course, it's somewhat a matter of taste whether a given problem is really "graph-theoretic" or not.)


2

Using the L'Hopital's theorem we have for $a>1$ $$\lim_{n\to\infty}\frac{\ln n}{a^{\frac n\alpha}}=\lim_{n\to\infty}\frac{\alpha}{n\ln a\cdot a^{\frac n\alpha}}=0$$ so for $\epsilon >0$ there's $n_0\in\Bbb N$ such that for $n\ge n_0$ we have $$\frac{\ln n}{a^{\frac n\alpha}}<\epsilon\iff \ln^\alpha n<\epsilon ^\alpha a^n=c \cdot a^n$$


1

Given the condition on the $A[i]$, this can be done very efficiently. Simply go backwards through the $A[i]$, incorporating each $A[i]$ into the sum if possible: remaining := x index_set := { } for (i = n to 1) if (A[i] <= remaining) remaining := remaining - A[i] Add i to index_set end if Then if remaining is zero, the solution ...


0

I guess this is what you are looking for.


-1

$(1+\epsilon)^n=e^{n \times log(1+\epsilon)}$ $=1+n \times log(1+\epsilon)+\frac{(n \times log(1+\epsilon))^2}{2!}+...,$ Taylor series $=1+n\epsilon+... ,$ Please develop this serie well to see what is happening, since $\epsilon^n\simeq0$ and $log(1+\epsilon)=\sum_{n=0}^{\infty}(-1)^n\frac{\epsilon^{n+1}}{n+1}$, the result then follow: ...


1

(Daniel Fischer wrote a comment with the same idea while I was typing this...) Quick and dirty: Turn the list of numbers into a string and hash it with a cryptographic hash function (such as SHA-2). Then hash the result again. Repeat this $n$ times. Use the result hash to create a number between $1$ and $10$, e.g. with something like a checksum. Do some ...


2

Convert the $x_i$ to strings, separated by ",". Then compute a good hash (for example, SHA-2) of the string and replace the first few characters by the hash. Repeat the latter very often, where the repeat count is adjusted to meet your 10 minute requirement. Then return $1+$ the hash modulo $10$.



Top 50 recent answers are included