# Tag Info

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 ...

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/...

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 ...

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.

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 ...

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}$ ...

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 ...

3

For a given $s$, you do $(|s|-1)n$ additions, not $|s|-1$ additions: you have to compute the inner sum for each $i\in [n]$. Thus, you are missing a factor of $n$.

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.

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:...

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 ...

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 ...

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

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 ...

1

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 ...

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 $+\... 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$.) 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 ... 1 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 ... 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 ... 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 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.

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[]...

Only top voted, non community-wiki answers of a minimum length are eligible