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


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


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


2

The RAM makes use of direct-memory-access, briefly this means that An element of data or instructions (such as a byte or word) can be directly stored or retrieved by selecting and using the locations on the storage media. Now this can be happened with the use of a DMA controller, which bypasses CPU to transfer data directly between I/O device and ...


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_{\...


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


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

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$


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


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


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)))$


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


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


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


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


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


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