Tag Info

New answers tagged

1

Hint: The power $j$ on $n^j$ in the denominator stays the same, but your power on the logarithm drops by $1$. What happens if you do this over and over so that the power on $\log$ becomes less than or equal to zero? Then you can put it in the denominator by switching signs on the power and hopefully be able to determine the limit from there, assuming $j > ...


1

Potentially yes. What you need is to raise the order of the formula when adding more points. Assume that we do not have to compute the nodes and the weights for any quadrature rule we're using. Using $n$ values on a segment $[a,b]$ one can numerically compute $\int_a^n f(x) dx$ with a gaussian rule with $n$ nodes. That rule would have an error of magnitude ...


1

Every planar map can be colored with $4$ colors. Moreover, a planar map with $n$ countries can be colored with $4$ colors in time $O(n^2)$. So $4$-coloring a planar map is a problem in $P$. On the other hands, not every planar map need 4 colors; some need only $3$ colors. But it is $NP$-complete to decide whether a planar map can be colored with $3$ colors. ...


0

I assume the task is generating a string representation of $A^k$. If $A$ has $n$ elements, we have to list $n^k$ tuples with $k$ components each. However the size of the numbers themselves grows with growing $n$, needing about $\log_{10}(n) + 1$ digits per component. So that will give an output of roughly $n^k k \log_{10} n$ digits.


0

It can be thought of as follows $T(n)=T(n-1)+3$---------exp 1. Now substituting n-1 in place of n in exp 1 $T(n-1)=T(n-2)+3$--------exp 2 Therefore, $T(n)=T(n-1)+3=(T(n-2)+3)+3=T(n-2)+6$ and so on....$T(n)$ can be written as $T(n)=T(n-k)+3k$


0

Let $f(k)$ be the number of coins needed. You need $\left\lfloor\frac{k}{200}\right\rfloor$ coins of value $200$. After that you need at most one coin of value $100$, nine coins of value $10$, and nine coins of value $1$, so $$\frac{k}{200}-1<\left\lfloor\frac{k}{200}\right\rfloor\le ...


0

Here's another place to start: http://www.thebigquestions.com/eorms.pdf Obviously, you should learn some basic game theory first, to understand the concepts before adding in quantum. I like Matthew Jackson's http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1968579. Hope this helps. Trurl.


1

The answer is no - the complexity class $\mathcal P$ consists of all problems that can be solved in polynomial time. In other words, a problem $P$ is in $\mathcal P$ if $$P(n) \in \bigcup_{k=1}^\infty O\left(n^k\right). $$ Suppose $f$ is a function defined on the positive integers with $f(n)\in O(n^k)$ for some $k>1$, but $f(n)\notin O(n^j)$ for $j<k$. ...


2

If $A$ has $n$ elements, $B$ has $m$ elements, $p$ are just in $B$, then $m-p$ are in both; and $n-(m-p)$ are just in $A$.


0

Suppose we have a triple of cities $(a,b,c)$ that form a triangle. If $d$ is a city with greater population than $b$ and $c$, then the triples $(a,b,d)$ and $(a,c,d)$ both have a bigger population than the original. One of those triples must be a triangle, since otherwise $b$ and $c$ would lie on the line connecting $a$ and $d$, meaning $a,b,c$ would be ...


0

I managed to come up with an acceptable proof (at least in my eyes). Would highly appreciate feedback. Let $A,B$ be cities and $S$ will denote the set of all cities. Suppose for a second that our solution must include $A$ and $B$, and our only free choice is in the third city. In this case, the best solution will be $A+B+C$ where $C$ is the city with ...


1

Let $(a, b,c)$ be the cities your algorithm finds. Let $(u,v,w)$ be an optimal solution (also ordered by decreasing population). Claim. $z_a=z_u$. Proof. Assume otherwise. Then $z_a>z_u\ge z_v\ge z_w$ and $(a,v,w)$ would be strictly better, which is absurd; hence $a,v,w$ are collinear. But then $(u,a,w)$ would be strictly better than $(u,v,w)$, qea. ...


1

The notion of how much time is taken should be defined to be somewhat independent of the machine, otherwise a machine that executes instructions faster would beat a slow machine that executes the same instructions. To do that we usually utilize Big-O notation which you can find on wikipedia. Also, we need a specific model of what instructions are allowed, ...


3

As pointed out in the comments a simplification obviates the need for Sterling's approximation: $$\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} = \mathcal{O}(n^2)$$


0

It somewhat depends on what you mean by "random array of integers". As pointed out, any comparison based algorithm needs $\Omega (n \log n)$ comparisons to sort in the worst case. However, if by "random" you mean that your integers are uniform independent random samples between some min value and some max value, then you can scan the array to find the min ...


3

This is only true for comparison-based sorting algorithms (*); these lectures notes by Avrim Blum give a proof, but any good textbook in computer science should provide one. At the very core, these arguments boil down to saying: "there are $n!$ possible permutations of $n$ elements, hence one needs $\log n! =\Theta(n\log n)$ bits to uniquely identify one. ...


1

Yes, and no. There's no known algorithm for finding a generator, but your chances of picking one at random ($\frac{\phi(p^n - 1)}{p^n - 1}$) are "pretty good" (I can't recall the exact limit for this expression, but I believe it's somewhere around 46%). It is not hard to see that this question is intimately related to knowing the exact distribution of ...


0

Below is the gist. Hope the loose but cleaner notation can help our memory. $\sum_i^n 2(n-i) (n-i+1)\approx2\sum n^2\approx2\int x^2dx\approx\frac{2}{3}x^3$ $\approx$ is in the sense of top term coefficient.


1

Well, $$ 2\sum_i^n (n-i)(n-i)+(n-i) = 2\sum_i^n (n-i)^2+2\sum_i^n(n-i) $$ Now, let's reindex these sums backwards so it's pretty. $$ 2\sum_i^n (i)^2+2\sum_i^n(i) $$ Now, if you know a little induction (or wolfram alpha) you can prove that $$ \sum_i^n (i)^2 = n^3/3+n^2/2+n/6 $$ and $\sum_i^n i$ is at worst $n^2$. So we have $\frac{2}{3}n^3$


1

An easy transformation ($j = n-i+1$) easily shows that \begin{align} \sum_{i=1}^n 2(n-i) (n-i+1) &= 2 \sum_{j=0}^{n-1}j(j+1)\\ &= 2 \sum_{j=0}^{n-1}(j^2+j)\\ &= 2 \left(\frac{1}{3} n^{3} - \frac{1}{3} n\right) \end{align} Then, since we are interested only in the asymptotic behaviour, we ...


1

For the first one, note that the $n$ factor is non relevant (since $nlogn$ is asymptotically larger), and then by opening the recursion you get that $$T(n)=T(0)+\sum_{k=1}^{n}klogk $$ which you could bound by $n^2logn$ and $\frac{n^2}{4}log{\frac{n}{2}}$ for upper and lower bounds respectively, which shows that $T(n) = \Theta (n^2logn)$. For the second one, ...


4

A dictionary with definitions is a directed graph where each word refers to the words used to define it (there should be no self references). We then try to find a maximal subgraph of this graph with the same vertices that has no cycles. Finding this set is called the "minimum feedback arc set problem" and it is NP-complete: ...


0

Yes, you're right -- though for large sizes you need to be a bit careful to avoid the entries of the partially-reduced matrix growing too large too fast.


2

The number of edges in a spanning tree of a graph $G$ is one less than the number of vertices of $G$.


1

By reduction from 3-colorability. This graph injects in your $G$ in exactly three different ways: If you have a graph that you want to 3-color, create one copy of the above hexagon for each of its nodes, and represent each of its edges by two successive edges -- e.g. like this if the original graph is a square with a diagonal: The direction of the ...


2

We assume that our numbers $(a_i)_i$ have at most $\alpha$ bits ($l(a_i)\leq \alpha$). We calculate the following values: $\gcd(a_1,a_2),{\rm lcm}(a_1,a_2),\gcd(\mathrm{lcm}(a_1,a_2),a_3),{\rm lcm}(a_1,a_2,a_3),\cdots $. When $a>b$, the complexity (number of elementary operations with respect to bits) $C_G(a,b)$ of the calculation of $\gcd(a,b)$ satisfies ...


1

You've not considered the cost for assignments and divisions. Anyway, let's ignore this part since it doesn't dominate the final complexity. Roughly, there are two mistakes in your calculation: $\langle Ap^{(k)}, p^{(k)} \rangle$: you first need to compute $Ap^{(k)}$, which requires $2n^2 - n$ operations, and then you need to compute the inner product of ...



Top 50 recent answers are included