New answers tagged

2

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$? It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k ...


1

If you consider space and time limitation, it'll be safe to assume that almost every Decidable problem (as per the exact definition) can have version that can be computationally not solvable. That said, Turing machines are not a practical model for computing. Even in the theoretical computer science community, the more realistic RAM machines are used ...


0

Here is an easy way to answer this kind of question. Modify the function so that it counts the number of multiplications it performs. This can be done in various ways, which I'll let you figure out. Alternatively, you can write a recurrence equation for the number of multiplications. Let us denote the number of multiplications when the argument is $n$ by $M(...


1

Wikipedia has a slight extension of the master theorem which covers your case: case 2b here. For the recurrence $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log_b a}/\log n)$, it gives $T(n)=n^{\log_b a}\log\log n$.


0

Your recurrence is $$ T(n) = \begin{cases} T(n-1) + n & \text{if $n>1$ is odd}, \\ 2T(n-1) + \log n & \text{if $n$ is even}, \\ 1 & \text{if $n=1$}. \end{cases} $$ We can convert it to a more amenable pair of recurrences. If $n > 1$ is odd then $$ T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1). $$ If $n > 2$ is even then $$ T(n) = 2T(n-1) + ...


1

Hybrid algorithms. In sorting algorithms it's rather common, Start with quicksort and if the size of the array is small enough switch to insertion sort (much faster for small $n$). Additionally when the recursion depth becomes too large (threatens to become $O(n^2)$) fall back to heapsort (guaranteed $O(n\log n)$).


2

What you are looking for is the so-called partition function (with some constraints on the addends). A simple upper bound is the number of solutions (and thus for the runtime since you generate all of them). For the unconstrained case this is $e^{c\sqrt n}$ as per Siegel with c=$\pi\sqrt\frac{2}{3}$. There are several specialised formulas with tighter ...


0

Even if i don't really understand your point, i'm try to figure out an intuitive proof for building heap time complexity, starting from a simple recursive algorithm for building heap. You have a collection of n unsorted element, called A, you want from this collection build a heap(in your case a min-heap because you are mantaining the minimum of collection ...


2

Remember that $\Theta(5n \log n^5) = \Theta(n \log n)$, since constant factors don't matter. Then $\Theta(n \log n) = \Omega(n \log n)$, by the definition of big theta. $\Omega(n \log n) = \Omega(n)$, because log is monotonic increasing (so we can remove it and still have a valid lower bound). Finally, $\Omega(n) = \Omega(n^{2/3})$, by the properties of ...


3

The solution is the recursive formula: $S[k] = \sum_{i=1}^mS[k-i]$ For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$. Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number ...


4

Try the following algorithm: For $1 \leq i \leq m$: $C[A[i]] = 0$ For $1 \leq i \leq m$: $C[B[i]] = 1$ Initialize answer to $0$ For $1 \leq i \leq m$: If $C[A[i]] = 1$ then $C[A[i]] = 2$ and increment answer Return answer


2

Under the assumption that $NP\neq \mathrm{co}NP$, we have that: $$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$ Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$. Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due ...


1

If you approximate this as an integral of the second for loop you get, substituting $k=(n-i)$: $$I_n = \int_1^n \frac{n+(n-k)^2-(n-k)+1}{k} dk = \int_1^n 1+\frac{(n-k)^2+1}{k} dk$$ according to WA, the corresponding antiderivative is of the indefinite integral is: $$(n^2+1)log(k) + \frac{1}{2}k(k-4n+2) +C$$ Thus, evaluating at $k=1$ and $n$ we get: $$...


2

I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward. For it to then still be a binary tree that node needs to be closest to the root in value. The worst case will turn out to be that all nodes have two ...


0

Usually dictionaries are not sorted. There are no provisions for accessing items in sorted order, and finding the predecessor and successor of a key take O (n) and are not really useful. What you do however is iterating through a dictionary, that is you have a loop that will visit each key, or each value, or each key-value pair in the dictionary exactly ...


1

It's true that on page 73, the author defines the abstract functions $Predecessor(D, k)$ and $Successor(D, k)$, which find the predecessor and successor of a given key. But the chart on page 74 lists the interfaces as $Predecessor(L, x)$ and $Successor(L, x)$, which find the predecessor and successor of a given entry index. Clearly this is O(1) for a ...


-1

I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows: 1. Consider the new array formed by multiplying the abssica array and the corresponding ordinate array and arrange it in ascending order. Next we arrange the abssica array and the ordinate array ...


Top 50 recent answers are included