New answers tagged

1

I am afraid that you fell prey to ambiguous notations. To clarify, the subscript $\frac{n-1}2$ in the recurrence relation, $T_n = T_\frac{n-1}2 + 1$ must mean the integer division of $n-1$ by 2 as used in most programming languages, i.e., $\frac 22=1$ and $\frac32=1$. The following equality does NOT hold, $$\log_2(\frac{n+1}{2}) = \log_2(n+1) - 1,$$ where ...


0

The approach you describe can be implemented to run in linear time. Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message. Store the bipartite graph in adjacency list format. Also keep track of the degree of each packet,...


2

Actually, for every combination of parenthesis, your algorithm performs $\Theta(n)$ amount of work (to build the string and append it to your list of combinations). The number of valid combinations of $n$ pairs of parenthesis is the $n$'th Catalan Number $C_n = \frac{1}{n+1}\binom{2n}{n}$. Thus, your algorithm runs in $\Theta(nC_n)$ which is also equal to $...


2

As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points). If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. Build a grid of $M \times M$ cells, then for each cell, compute the list of points inside (doing one loop on points $O(N)$). Finally you just have to compare ...


2

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$. Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$


0

Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c*n^2, if we have 4*n^2 and 1/4*n^2, still 1/4*n^2 is 16 times faster !! A very important point is that your second algorithm seems to use divide and conquer method. ...


0

The worst case complexity of FC-MRV is $O(n^2 d^2)$ where $n$ is the number of variables and $d$ is the number of domain size.


0

Store the window in a balanced binary search tree. Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it. Each of those operations can be done in $O(\log k)$ time, so the total running time to process $n$ items will be $O(n \log k)$.


2

You had several questions in there, let's just look at a couple of them, the way I understood you. Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard? Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the ...


4

Here are the functions. $$f(n) = \frac{\log(n)}{\log\log(n)}$$ $$h(n)=\frac n{f(n)}=\frac{n\log\log(n)}{\log(n)}$$ $$g(n)=f(h(n))=\frac{\log(\frac{n\log\log(n)}{\log(n)})} {\log\log(\frac{n\log\log(n)}{\log(n)})}$$ Is $g(n) < f(n)$ in fact true (starting from some $n$)? Yes, here is a proof. Let us compute the derivative of $f(x)$ with ...


0

Welcome on CS. It seems that the concept of temporal complexity of an algorithm is a little unclear to you. There is no thing like "unity of time". We are concerned with how the computation of a function (measured in number of operations of a Turing Machine and not in seconds or other time units) grows with increasing input. In the case of your example the ...


1

The total running time of $𝐴_3$ will be bounded by $𝑝(𝑥)+𝑞(𝑦)$ where $𝑥$ is the size of the input to $𝐴_1 $and $𝑦$ is the size of the output of $𝐴1$. Now time complexity is usually written in terms of the size of the input of the algorithm and nothing else, so if $𝑦=𝑓(𝑥)$ then the running time of $𝐴_3$ will be $\mathcal{O}(p(x)+q(f(x)))$


2

If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.


1

I don't think you're likely to find any such proof. Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise). If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$) yet $\...


3

Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to consider case 3 of the Master Theorem since $f(n)=\Omega(n)$. However, the theorem requires that there exist an $\epsilon > 0$ such that $n\;log\;n = \Omega(n^{1+...


1

There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$. One can prove this with an adversarial argument. Consider running the algorithm on the following input: Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$. Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on ...


1

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has ...


2

$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon > 0$. This is true for any $c \geq 0$, including $c < 1$. For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$. This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log ...


-2

If there exists an algorithm that solves NP-complete in P time and space then the values computed cannot grow exponentially. A problem in which the values computed grew exponentially would not be an NP-complete problem, as it could not be reduced to SAT by any P complexity algorithm. The answers that the problem and not the algorithm are defining of ...


-3

There are problems for which there is no reduction to SAT that is of P complexity. Those problems may or may not be solved by computations that can be performed in O(2^n) or less time and space. SAT is always worst case O(2^n) or less by definition. SAT has a P complexity solution. See arxiv.org/abs/cs/0205064.


1

It is $\mathcal{O}(y + n^{2})$, as the first loop does $\mathcal{O}(n)$ operations and increments $y$ by $\frac{n(n+1)}{2} = \mathcal{O}(n^{2})$, and the second loop does $\mathcal{O}(y')$ operations, where $y' = y + \frac{n(n+1)}{2}$ is the modified value of $y$.


2

Let us describe an NTM $N$ that computes $L_1$ in polynomial time. The machine "guesses" the first $n - |w|$ letters of a word $x'$ (it makes all possible guesses non-deterministicly) and append $w$ to $x'$ then it simulates $M$ on the resulting word. If $M$ accepts on any of the guesses the machine $N$ halts and accepts. If all reject, $N$ also rejects. ...


3

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each ...


0

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient. There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or $$C_n = \prod_{k=2}^n \frac{n+k}{k}$$ The problem with writing down the time complexity for computing these numbers is that the ...


1

We want to swap array elements so that in the end, A[1] = 1, A[2] = 2, ..., A[n] = n. There are at most n items in the wrong place. Every swap exchanges two elements that are both in the wrong place, and moves at least one into the correct place. After n swaps all elements are in the right place, and at this point there will be no further swaps. Therefore ...


0

I'm not 100% sure on this, but I believe that the best known bound on this comes from the construction used for the best known bound on creating oblivious Turing machines. See this Gödel's Lost Letter blog post on the relationship between circuit size and oblivious Turing machines, and in particular the "Open Problems" section. Given an arbitrary ...


1

It sounds like your pseudocode is equivalent to the following: Do search for low in the BST. Find this value or the next largest value. (assuming that the BST is somewhat balanced, this is $O(lg(n))$) In-order traverse until we reach an element that is greater than high, adding all values that we traverse to some running sum. (in order traversal of $m$ ...


2

We can write each permutation of $1,\ldots,n$ in cycle notation, which will help us understand the behavior of the algorithm. Suppose that $i = 1$. If $1$ is a fixed point, then the algorithm simply moves on. Otherwise, suppose that the cycle involving $1$ is $(1\;a_2\;a_3\;\cdots\;a_\ell)$, which means that $a_2 = A[1]$, $a_3 = A[2]$, ..., $a_\ell = A[a_{\...


1

The $\log T(n)$ factor in the analysis stems from the need to keep (and update) a step counter, in binary, that goes up to $T(n)$. This requires $\log(T(n))$ cells, and the need to update it (or rather, to drag it along on the tape) costs $\log(T(n))$ in every iteration. Now, if you could avoid this for $\epsilon$, then you could avoid it for an arbitrary ...


Top 50 recent answers are included