New answers tagged

0

Regarding the specific problem you pose about whether the bit of a number can be permuted to give a prime, I believe the following to be an algorithm in P. If the number has fewer than 100 zeros in it or fewer than 100 ones in it, enumerate all permutations and test them all for primality using a primality test (e.g. AKS) and output accordingly. Otherwise ...


0

o(n^2) means that n^2 is an upper bound. So even if it is smaller than n^2 but not so far from it, it still is o(n^2). Like 1/2 n^2 is also o(n^2)


2

It's not clear what you think $O(n^2)$ means. $O(n^2)$ means that there is a constant $c$ so that, when $n$ is large enough, your algorithm takes at least $cn^2$ time. As you observed, the algorithm takes $(n-1)+(n-2) + \ldots + 1 $ time. This is equal to $\frac12 (n^2-n)$. This quantity is larger than $\frac14n^2$ whenever $n$ is larger than $10$. So ...


6

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ ...


0

Your problem is equivalent to determining the number of edges in a complete graph with $n$ nodes and undirected edges. Model each point as a node of a graph. You now have a graph with $n$ nodes. You have to look at the relation between every pair of nodes. This is equivalent to iterating over all edges precisely once. That means that you need to consider ...


1

Here's a hint. Break the question into two parts: Given $n$ elements, compute the (exact) number $C$ of comparisons following your scheme. If you are stuck here, (i) look at gradually growing examples and see how $C$ behaves and (ii) try to express $C$ as a sum and perhaps use a suitable sum identity. Prove that $C = O(n^2)$.


1

In short and simple, I will show you why. Suppose, you have a factorization algorithm. Except for the small difference that one accepts integers for input and the other $Tally$. As you can see both code snippets are similar. x = input integer factors = []; for i in range(1, x + 1): if x % i == 0: factors.append(i) print(factors) Notice that ...


0

Your algorithm is incorrect. Think about the minimal DFA for $ab^*c$. Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.


4

Here are the values of $j$ at the end of each iteration: $$ 1,3,6,10,15,21,28,36,45,55,\ldots $$ More generally, after $t$ iterations, $j = 1 + \cdots + t = \binom{t+1}{2} = \Theta(t^2)$. Therefore the loop halts after $\Theta(\sqrt{n})$ iterations.


2

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete. On the other hand, exhaustive search is not ...


2

Let us start with a solution using $n$ processors and then we optimize the solution to use $O(n/\log n)$ of them. Assume first that $n$ is a power of $2$, i.e. $2^k$ for some $k \in \mathbb{Z}$. Imagine a perfect binary tree where the leaves are the elements of the array. In each step we will process one level of the tree in a bottom up manner, where for ...


0

Take Ack(n-1). Grows much slower than Ack(n).


1

Since the graph is complete, you can connect each vertex with any other vertex. Note that each vertex must be connected to the tree and hence has an incident edge in the tree. Assuming all weights are positive, choose a vertex $v$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $v$ ...


1

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP). Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as ...


0

Here's a different way of proving that $0.01 \log n - 2000n + 6$ is $O(n \log n)$. If $f$ and $g$ are monotonically increasing functions and there exists some $x_0$ such that $g(x_0) > 0$, then $f \in O(g)$ if and only if $\exists a, b \colon \forall x \colon f(x) \leq ag(x) + b$. (Proof left as an exercise to those readers who feel up to the challenge. ...


0

Definition of big-O with c = 0.01 and n0 = 1. For a proof of big-theta you’d show the limit of f(n) / (n log n) exists and is > 0. If you had the function f(n) = 0.01 n log n + 2000n + 6, where c = 0.01 doesn't work, a nice large c = 2019 will make the O(n) proof very easy.


1

On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have $$ T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = [\tfrac{5}{6}C+1]n. $$ (We're cheating here a bit ...


0

Defining base cases: $T(0) = 0;$ $T(1) = 0;$ I got: $$ T(n) = n \; (\sum_{r = 0}^{log_3 \; {n}} [ \binom{log_3 \; {n}}{r} \; log_2 \; [{(\frac{2}{3})^r \; n}] \; + \; \sum_{r = 0}^{log_2 \; {n}} [ \binom{log_2 \; {n}}{r} \; log_2 \; [{(\frac{3}{2})^r \; n}]) $$ $$ $$ You can do the approximation & the bounding yourselves. Sorta took me longer to ...


1

These problems can be solved efficiently. For Problem 2, both [1] and [2] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices. For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see [3]) that a Hamiltonian path is ...


2

We just have one comparison when $n$ is odd. So, the total complexity is (if we suppose $n$ is even, w.l.o.g.): $$T(n) = \frac{n}{2} + (n +‌ (n-2) + (n-4) + ... + 2) $$ $$= \frac{n}{2} + 2 \sum_{i=1}^{\frac{n}{2}}i = \frac{n}{2} + 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \Theta(n^2)$$


1

You should also look at what you actually want to achieve. The coefficients can grow very quickly, meaning that evaluating the polynomial can have large rounding errors. Given the roots, you can evaluate the polynomial quite quickly without knowing the coefficients, and with high precision.


21

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method. First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the ...


0

With the help of Steven, i am posting the solution. def divide(dd,dr): ''' let dd and dr be the dividend and divisor x be the current macium divisor, less that dividend c be the counter q is the qutotient ''' x=dr c=0 while (x<<c) <= dd: c+=1 print(c) q=0 #...


2

It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$. The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration. The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{...


1

Here is a strategy (I will only consider positive numbers): Let $d$ be the dividend and $x$ be the divisor. Generate all values $x_i = 2^i x$, up to some some $x_k$ such that $x_{k+1}$ exceeds the dividend. This can be done with only one addition per value since $x_{0} = x$ and, for $i \ge 1$, $x_i = x_{i-1} + x_{i-1}$. Similarly, generate all values $b_i = ...


1

It depends on which data structure you use to store the graph. For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}[i]$ as $\texttt{...


1

As you mention, you can show inductively that $T(n) = T(n^{1/2^k}) + kc$, with base case $T(n) = O(1)$ for $n \leq 2$ (say). It follows that $T(n) = \Theta(\ell)$, where $\ell$ is the minimal number such that $n^{1/2^\ell} \leq 2$. Taking a log, we get $\frac{\log n}{2^\ell} \leq 1$, or $\log n \leq 2^\ell$. Taking another log, we get $\log \log n \leq \ell$....


2

Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows: $$ Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c. $$ Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back: $$ T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n). $$


1

Define S(k) = $T(2^{2^k})$. Then S(k) = $T(2^{2^k})$ = $T(2^{2^{k-1}}) + c$ = $T(2^{2^{k-2}}) + 2c$ = ... = $T(2^{2^{k-k}}) + k\cdot c$ = $T(2) + k\cdot c$.


1

Use the following strategy $S$: Put each card $c$ on the stack with the smallest top card $c'$ such that $c' > c$. Consider a generic strategy $T$, and iteratively simulate $S$ and $T$. Let $s_i = (s^i_1, s^i_2, \dots, s^i_{h_i})$ be the values on the top of the stacks after placing the $i$-th card $c_i$ according to strategy $S$, in increasing order. ...


2

I shall modify the question a bit and answer the following version, which I think is more correct: Prove that the lower bound of any character-comparing string sorting algorithm is $\Omega(d + n \log n)$, where $d$ is the sum of the lengths of the distinguishing prefixes of all the strings in our set $S$ and $n$ is the cardinality of the strings set $S$. ...


2

The time complexity you indicated is the lower bound of your specific problem. A lower bound is the worst-case running time of the most optimized TM that recognizes membership in the language. Lover bound for sorting algorithms is $\Omega(n \log n)$ this means that it is not possible to do better than this and all the sorting cases (instances) may have a ...


3

This is algorithm called bucket sort, integer sort, counting sort, or Pigeonhole sort (naming is a bit inconsistent across sources and/or different names refer to slight variations of the same idea). Its time complexity is $O(m)$ (assuming distinct values) where $m$ is the largest among the $n$ integers you are trying to sort. Your algorithm takes $O(n)$ ...


1

You can find all of these order statistics in $O(n)$. First, find the maximum (order statistic $2^k$) in time $O(n)$. Then, find the median (order statistic $2^{k-1}$) in time $O(n)$, and remove all larger elements. Find order statistic $2^{k-2}$ in time $O(n/2)$, and remove all larger elements. And so on. The total running time is $$O(n + n/2 + n/4 + \cdots)...


3

Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.


2

I will suggest a similar strategy. Note that your strategy yields a constant factor better than the one presented here but the proof is more technical. Let us divide the strategy in rounds $1, 2, \dots$, where in round $i$ we go $2^{i-1}$ steps to the right, then we go back to the center and we repeat the exact same to the left. This means we go one step to ...


0

Your approach is correct. Without loss of generality, suppose that $2^{2n-1} < x \le 2^{2n+1}$. Now, if you count the number of steps needed to find $x$ with your algorithm, you'll find out that it contains the sum of geometric progression which can be bounded by $2^{2n+3} = 16\cdot 2^{2n-1} = O(x)$ since $2^{2n-1} < x$.


0

If you had a "black-box" min heap where the only operations available to you are adding elements and extracting (reading and simultaneously removing) the smallest item, then the time complexity is O (n) obviously. It is imaginable that you have a specific implementation where even finding the second smallest element cannot be done in constant time. You ...


0

The assumption is: You have an "equality" operator. The equality operator follows the usual rules, and it is also stable over time: If x = y or x ≠ y today, then x = y or x ≠ y tomorrow as well. You need a hash function which is guaranteed to hash equal values to equal hashes. Since equality is stable over time, if hash (x) is calculated and stored today, ...


1

Suppose the objects you want to compare are strings containing terminating programs that output either 1 or 0 (and written in Visual Basic, because why not), and the equality function returns true if and only if the output of the two programs given as operands is the same. (The termination assumption is there to ensure that this equality is well-defined.) ...


1

If we draw recurrence tree for this relation than it would be something like following: T(n) -> Cost: n / | \ T(n/2) T(n/3) T(n/6) -> total cost: n/2 + n/3 + n/6 = n . . T(1) ---------------> highest depth which is about lg(n). So, there are $lg(n)$ levels and every level has at least cost $n$ so $T(n) =...


3

If you don’t know the equality function then you let hash(x) = 0. Seriously. All your algorithms will work, but slowly because of collisions. All the other suggestions will make your hashing slow instead so you lose nothing. Actually, if you have multiple dictionaries containing these keys, operations are quadratic in the size of each dictionary, instead of ...


5

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$. Then, the trick is, instead of ...


0

Let $k_i = 2^i$, and define $m$ to be the minimum value such that $n-(m-1) \leq k_m$. It's not hard to check that the running time of $f_2$ is $\Theta(k_1 + \cdots + k_{m-1})$. Since $k_i$ grows exponentially, $k_1 + \cdots + k_{m-1} = \Theta(k_m)$, and so the running time of $f_2$ is $\Theta(k_m)$. It remains to find the minimum integer value of $m$ which ...


1

A unary language is a subset of $\sigma^*$ for some letter $\sigma$. If your language is of this form, then it is unary. Otherwise it isn't. A unary encoding is an encoding of some data as a subset of $\sigma^*$. For example, one possible unary encoding of the natural numbers is $n \mapsto 1^n$. Any language in which instances are unary encoded is a unary ...


0

Ok this is not a good way to do it but here is my approach. So, here it suffices to prove $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$. That will imply $f(n) = o(g(n))$ proof of $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$ $\lim_{n\to\infty} \frac{f(n)}{g(n)}$ $= \lim_{n\to\infty} \frac{(log(n))^{100} + n^{0.01}}{(log(n))^{50} + n^{0.05}}$ $= \lim_{n\to\...


Top 50 recent answers are included