New answers tagged

1

Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes): The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many ...


2

An obvious counter example is $g(n) = \sqrt{n}$. If $f(n) = \Theta(\sqrt{\log n})$, you can't conclude that $f(n) = \Theta(\log{\sqrt{n}}) = \Theta(\log{n})$.


6

Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for any problem in NP, not just SUBSET-SUM.


2

A very simple proof: I claim that if there are d integers with values between x and y, and there are n ≥ 2 elements in the array, then the probability that x and y are compared is 2 / (d + 2), independent of n. Proof by induction: If n = 2 then clearly d = 0, so the claim is that x and y are compared with probability 2 / (0 + 2) = 1. This is also clearly ...


0

Sounds like you want a solution for bounded integers, 32-bit for example. If so, any sorted dictionary whose complexity depends on the key length only will do what you want. Two examples are binary trie and van Emde Boas tree.


2

The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is ...


0

One thing before I explain: HashMap doesn't use an array that big, it uses chaining, which is another concept you'll have to look up. And if you're talking about creating an array size 2 billion, that still won't work because you still have to scan the 2 billion entries in the array. Ok, technically that's O(1), but only because O(2 billion) is counted as O(...


0

The speed issue would depend on the hardware / processor. For CRC, what is needed is carryless multiply (CLMUL), and I assume most processors that have carryless multiplies, which date back to 2008 for X86 processors (pclmulqdq using xmm registers) the multiply time is fixed. For a typical hardware implementation, since the multiply is carryless, there's no ...


1

No, it doesn't prove that P = NP. This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness. The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard. Presumably, choosing a hypergraph at random is very ...


0

Using Dr. John's algorithm, you could sort arrays in time $O(n\log\log n)$ (use the hint, choosing the value of $t$ which allows you to apply the hint), and this is a problem (why?).


0

It sounds like you almost have an algorithm. Find the vertex $u$ where the successor of $m$ is stored. Similarly, find the vertex $v$ where $n$ is stored (or its predecessor if $n$ is not in the BST). Suppose that the range of vertices to delete is not empty (that is, the key of $u$ is smaller than, or equal to, the key of $v$) and let $w$ be the lowest ...


2

Your bipartite graph describes a set system whose elements are the vertices in $V_1$ and whose sets are the vertices in $V_2$. Your condition is the same as asking whether the discrepancy is at most $1$. If all sets have even size (i.e., all vertices in $V_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a ...


1

Use BFS, and keep prev pointers. Good textbooks will have a chapter on shortest-path algorithms where they describe how to reconstruct the paths themselves (not just the distances) using prev pointers; use that method, and then you'll be able to reconstruct a shortest path from $X$ to any other node. Initially the estimated distance to all nodes is $+\...


0

I like this one: given a string $S$, find the longest substring that appears two or more times in $S$. There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring. However I don'...


2

I could think of a time-efficient solution which is not good in terms of memory. We will carry out duplication of the given array. For eg. Initial Array: We can have 4 duplicate copies of the same array, each attached to form a huge square. Big Array looks like: Within this Big Array, let me call my result as the Result Array. Initially, when we ...


1

Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$. (Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C>0$.)


0

For each value of $j$, the inner loop runs for $O(N/j)$ iterations. Fixing $i$ and varying over all $j$ in the middle loop, the total number of iterations in the inner loop is $$ O(N/i + N/(2i) + N/(3i) + N/(ki)) = O(N\log k/i), $$ where $ki$ is the maximal multiple of $i$ which is at most $N$. We can bound $k$ by $N/i$, and so the expression above equals $O(...


0

The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease. Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$. (For simplicity I represent hard ...


4

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.


1

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized". The amortized cost per items is O(1), since the cost of adding n items individually is O(n). There are various ...


2

No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$. No, it certainly does not have the same runtime. See Sorting functions by asymptotic growth. There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably ...


0

The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent_set_(graph_theory) or set packing. One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$. Note that $\|\sum_i ...


3

No way to say. $T(n) = O(n \log n)$ means there exist constants $c > 0, N_0$ so that for all $n \ge N_0$ it is $T(n) \le c n \log n$. They are anything, i.e., it might be valid only for ridiculously large $n$ (large $N_0$), or even for small $N_0$, like $N_0 = 10$, the constant $c$ could be such that all you know is that $T(100) \le \text{one milisecond}$ ...


2

If $n\log n = x$ then $x = e^{\log n} \log n$ and so $\log n = W(x)$, where $W$ is the Lambert $W$ function. The Lambert W functions is implemented in any popular mathematical software. It can be evaluated using standard techniques such as Newton's method or its second derivative generalization, Halley's method; see the Wikipedia article (under Numerical ...


2

It seems like none of the other answers so far have mentioned a basic reason: There are many sorting algorithms whose total (asymptotic) time complexity is in fact bounded by the number of comparisons times the maximum time taken per comparison. Obviously that is why such sorting algorithms' cost should be measured by the number of comparisons, because they ...


2

Big Oh analysis is looking at the asymptotic behavior of an algorithm. In these analyses, the thing which gets done "more" will always overshadow the thing which gets done less. As an example, consider an algorithm which does $O(n)$ disk operations at a cost of 1,000,000,000 units each, and $O(n^3)$ comparisons at a cost of 1 unit each. Obviously for ...


1

1. Because you can avoid the other operations being expensive. Comparing integers is cheap. Comparing arbitrary elements of type T is typically as expensive as reading sizeof(T) bytes. Now, you might think "ok, but copying type-T elements is also expensive" - but we don't need to do that. We can just copy or move their indices in the input around and use ...


0

The cost of comparison is more complex and depends on more than you imagine. Between each of the following is an order of magnitude cost increase. Register CPU Cache RAM Magnetic disk Then there's the fact that your process does not run in isolation, but competes with other processes for system resources. Some of those processes will not be denied. In the ...


6

what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? Um, yeah. That's why, in such cases, we do use those other operations for the analysis. For example: Binary insertion sort employs a binary search to determine the ...


9

If moving an item were n times more expensive than comparing, selection sort would suddenly be the most efficient algorithm. But if moving an item were expensive, we could sort an array of array indices, and then sort the original array in place with at most 1.5n moves. (That would actually be n/2 swaps; if a swap is cheaper than 3 moves then worst case is 4/...


3

For 3SAT, the number of variables is polynomially related to the number of clauses. (See the end for the justification.) Consequently, any algorithm for 3SAT whose running time is polynomial in the number of clauses would also be polynomial in the number of variables; and any algorithm for 3SAT whose running time is polynomial in the number of variables ...


22

Sure. But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about. This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running ...


1

It is $NP$ as $SAT$ can be polynomially reduced to this problem. Let clauses be the left part vertexes, and literals be the right part vertexes. Draw an edge $(x,y)$ iff clause $x$ contains literal $y$. Finally, a pair of edges $(x_1, y_1)$ and $(x_2, y_2)$ will be exclusive iff $y_1$ corresponds to literal $a$ and $y_2$ corresponds to literal $\overline{a}$...


1

The inner loop will iterate once with $j=i+1$, once again with $j=i+2$, and so on, up to the last iteration with $j=n-1$, so there will be, for each $i$ in the outer loop, $(i+1)-(n-1)-1=n+i-1$ time contributions from the inner loop. Add these to get your answer.


3

NP-completeness is a category of decision problems, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete. There are other types of problems around. The three most common ones are optimization problems, function problems and search problems. Optimization ...


3

Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression ...


2

Check Belare and Goldwasser, "The complexity of decision versus search", SIAM J. Of Computing, 23:1 (feb 1994), pp. 97-119. Belare has notes for a class.


4

The optimization function is designed in a way to find a solution that: uses a small number of lines is balanced (the number of extra spaces at the end of each line should be about the same length) Lets look first at the linear optimization function, i.e. the sum of all extra spaces. It is very clear, that the optimal solution under that function is one ...


1

You should measure the length of the output in the same way you measure the length of the input. For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$. The factorial function, in contrast, has much too long output length. Indeed, if the input ...


1

This answer is very similar to Massimo's except with a (hopefully) simpler style/structure of phrasing it and in addition includes the solution to find the second weighted median as well. If you want just a hint, just look at step 1), and read no further. If you want more hints, continue to next step. Assumptions: Input is in two different arrays: Prices[]...


2

Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete. Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:...


Top 50 recent answers are included