# Tag Info

## New answers tagged time-complexity

1

1.) If we look at $n=8$ then we see: $$\frac{1}{2^4}\times\left((n-6)(n-5)(n-4)(n-3)(n-2)\right)\times \left((n-5)(n-4)(n-3)(n-2)\right)$$ $$=\frac{((n-2)!)^2}{2^5}.$$ Therefore we can formulate $f_n(n)$ as follow: $$f_n(n)=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i^2$$ $$=\frac{n-(n-2)}{2^{n-4}}\times \prod_{i=3}^{n-2}i\times \prod_{i=3}^{n-2}i$$ $$=\... 1 Your algorithm Z doesn't decide A. If the input is in both A and B, then it returns "no" even though the correct answer is "yes." The error can't be fixed, since it's generally impossible to deduce whether an input is in A if you only know its membership status in B and A \setminus B. 2 It seems that:$$ f(n) = \left( 2\prod_{i=3}^{n-2} i^2 \right) \cdot \frac{1}{2^{n-4}} = \frac{1}{2^{n-5}} \cdot \frac{1}{2^2} \cdot\prod_{i=1}^{n-2}i^2 = \frac{1}{2^{n-3}} \cdot \left( \prod_{i=1}^{n-2}i \right)^2 = 2^{3-n} ((n-2)!)^2. $$This time complexity is superexponential. Indeed, using Stirling's approximation:$$ 2^{3-n} ((n-2)!)^2 \sim 2^{3-n} \...

1

Take $B=\Sigma^*$. Obviously, $A\setminus B=\emptyset$ is not NP-complete. I'm not sure how concatenation has anything to do with set subtraction, but obviously, concatenating $B=\Sigma^*$ to $A\setminus B=\emptyset$ won't yield $A$ back, since $\Sigma^* \emptyset=\emptyset$ as $\emptyset$ doesn't contain any words.

1

Let $C$ be any language in $NP \setminus \{ \emptyset \}$. Notice that such a $C$ exists (e.g., $C = \Sigma^*$). The claim "if $A$ is $NP$-Complete and $B$ is in $P$ then $A \setminus B$ is $NP$-complete" is false (regardless of whether $P=NP$). To see this pick $B=\Sigma^*$. Then $A \setminus B = \emptyset$. Since there is no polynomial-time ...

2

Your counter-example isn't true. Let $f(n)=2^n$, we see that $$f(\frac{n}{2})=2^\frac{n}{2}=\sqrt{2}^n.$$ As a result we show that $f(n)\neq\Theta(f(\frac{n}{2}))$ $$\lim_{n\to \infty}\frac{f(n)}{f(\frac{n}{2})}=\frac{2^n}{\sqrt{2}^n}$$ $$=\frac{2}{\sqrt{2}}\times\dots\times\frac{2}{\sqrt{2}}$$ $$=\frac{\sqrt{2}}{1}\times\dots\times\frac{\sqrt{2}}{1}$$ $$=\... 0 Lets look at the (worst-case) recurrence for bt:$$ T(n) = \sum_{l = 1}^{n} (O(l) + T(n-l)) $$Here n measures the length of the string passed to bt. The sum basically represents the complexity of the loop; for every l you do a O(l) compare operation and in the worst-case call bt with a string of length n-l. However we can simplify the above relation ... 2 Alright, we are given a language C \in \mathrm{P} and a language A \in \mathrm{NP}, and we are promised that C \leq_p A. What can we conclude? First a side remark: The reduction C \leq_p A tells us very little since we know C \in \mathrm{P}. The only extra information we get is that if A is empty, then so is C, and if A = \Sigma^*, then C = \... 1 Here is a quick formal proof without limits. Choose c=\frac{1}{4} and n_0=4. For n \ge n_0:$$ n^{5}-3n^{4}+\log n^{10} > n^5 - 3n^{4} = n^4 \cdot (n-3) \ge n^4 \cdot \frac{n}{4} = \frac{n^5}{4} =c n^5, $$where we used the inequality n-3 \ge \frac{n}{4} or, equivalently, \frac{3}{4}n \ge 3. 4 Definitions I'm using the definition of big-omega from Wikipedia and making it more explicit:$$\left[ f(n) \in \Omega(g(n)) \right] \:\Longleftrightarrow\: \left[ \exists k \in \mathbb{R}^+, \exists n_0 \in \mathbb{N}, \forall n \in \mathbb{N}, \left[(n > n_0) \Rightarrow (f(n) \ge k \cdot g(n)) \right] \right]$$In your statement you have f(n) = n^5 - ... 1 Below method, solve your problem in \mathcal{O}(n), and additional space \mathcal{O}(n). Use Selection algorithm to find (\log n)^{th} largest element in worst case \mathcal{O}(n). Then your array become below form : That we partition the array in term of (\log n)^{th} largest element. Now all elements in L are greater equal to (\log n)^{th} ... 1 With small n Big \Omega it is just about useless and it's the hidden constants, so we suppose n\to \infty. At this situation, the term n^5 dominate other terms, and we can conclude that n^5=\Omega(n^5). Note that, if number of functions are constant ( in the below k is constant) that has below form:$$f_1(n)+\dots+f_k(n)$$and suppose f(n) is ... 6 Let me suggest direct simple solution: definition of \Omega contains 2 bound variables c and N. In simple cases, as is in OP, we can choose one and solve second from expression obtained from definition. Obviously for left side we need constant less then one, so taking, for example, c=\frac{1}{10} we have$$n^{5}-3n^{4}+\log\left(n^{10}\right) \...

5

Just apply the definition. So in this case, we must have that $\lim_{n \to \infty} f(n) / g(n) > 0$ in order for $f(n) = \Omega(g(n))$. Let's plug in what you have and observe that $$\lim_{n \to \infty} \frac{n^{5}-3n^{4}+\log(n^{10})}{n^5} = 1 > 0.$$ This completes the proof.

1

Let $\ell_x$ be the left sub tree at node $x$, Let $r_x$ be the right sub tree at node $x$. So the size of $\ell_x$ is $\mid\ell_x\mid$, and size of $r_x$ is $\mid r_x\mid$. Let $T(n)$ be number of nodes our procedure visited during in-order traversal. So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r_x\mid)$, because ...

1

It's possible that, describe your recurrence as summation: $$T(n)=T(1)+\sum_{i=0}^{\log n}c_1\left(\frac{n}{2}\right)^2\times\left(\frac{1}{2^i}\right)+ \sum_{i=0}^{\log n}c_2\left(\frac{n}{2^i}\right)$$ $$=\hspace{4pt}T(1)+\sum_{i=0}^{\log n}c_1\left(\frac{n^2}{2^{2+i}}\right)+ \sum_{i=0}^{\log n}c_2\left(\frac{n}{2^i}\right)$$ $$=\hspace{4pt}T(1)+c_1n^2\... 1 It's possible to sort your array in linear time by using a method that use comparison based and non-comparison based sorting algorithms as subroutines. First, do a linear scan to find all integer number in range [\sqrt{n},n\sqrt{n}] and put those elements into array A', and put \sqrt{n} remaining elements into an array A^{''}. The running time of ... 0 Well, in theory the first one is O(\log n). In practice, if n < 2^{64} for example, it is a fixed number of operations on a 64 bit processor. Likely to cost 1 or at most 2 nanoseconds. (And I would write it as (x & (x-1)) == 0 && x != 0, so the comparison x != 0 isn't done for all numbers, but only for numbers that are either powers of two ... 2 In the RAM model with uniform costs and word size \Omega(\log n) the first algorithm requires O(1) time since each word operation takes constant time. The second algorithm requires time O(\log n) since each iteration can be performed in O(1) time and there are at most O(\log n) iterations (after each iteration the value of n is at most half the ... 4 Brute-force algorithms can be considered as a good example to achieve the mentioned running times (i.e. \Omega(n^4)). Suppose given the sequence \sigma=\langle a_1,a_2,\dots , a_n\rangle of real numbers, you want to find, if exists k elements (k\geq 4, and k is constant ) from \sigma such that$$\sum_{i=1}^{k}a_i=0.$$Obviously, a simple ... 1 I assume that by "verses" you mean boolean formulas. The language is definitely in CO-NP since a "no" certificate is a satisfying assignment. Currently we don't know whether FALSE is in P nor whether it is in NP. 3 In the word RAM model, any pure function which takes a constant number of machine words and returns a constant number of machine words is assumed to cost O(1) time. This is because any such function could, in principle, be implemented as a static memory lookup or a new CPU instruction. If you're asking about the complexity of a specific algorithm, then ... 1 Assuming words cant overlap, we will prove that the statement is false. Lets try to think about \Sigma^* and see what happens (since as you said, it could be used to create a polynomial counter for all other languages in P). Without loss of generality, we can assume that the polynomial counter will contain the words in increasing lexicographical ordering ... 1 The following assumes that words cannot overlap on the output tape. Let \Sigma=\{0,1\}, pick \Sigma^* \in \mathsf{P} as your language and suppose that there is a polynomial counter T for \Sigma^*. Let p(|w|) = |w|^{c_1} + c_2 with c_1, c_2 \ge 0 be a polynomial for such that a word w \in L starts in position at most p(|w|) on the output tape ... 2 By Jensen's inequality you have:$$ \frac{1}{m} \sum \log L_i \le \log \left( \frac{1}{m} \sum L_i \right) =\log\left(\frac{n}{m}\right). $$Therefore \sum \log L_i \le m \log \frac{n}{m} and the overall time complexity is O(m \log \frac{n}{m}). Notice that this upper bound is tight (for example when all L_is are roughly equal). 4 Your solution is wrong. In particular the Betweenness problem is not what you claim it to be. In the Betweenness problem you are given a collection of triples (x_i, x_j, x_h) and you want to place x_j between the occurrences of x_i and x_h. Notice that there is no requirement saying that x_i must precede x_j. I.e., both \langle x_i, \dots, x_j, \... 5 Your problem can be solved in linear time. Construct a directed graph on the vertex set \{1,\ldots,n\}, with an edge i \to j for every comparison x_i < x_j. There is a linear order compatible with the given comparisons iff the digraph is acyclic. (See topological ordering.) 1 From the definition of big-O:$$f(n)=\mathcal{O}(n)$$if there exists a positive constant real number c that$$ f(n)\leq cn.$$I claim that$$\frac{n}{\log n} \log \frac{n}{\log n} = \mathcal{O}(n)$$So, for proving it we act as follow$$\frac{n}{\log n} \log \frac{n}{\log n} \leq cn$$multiply each side of inequality by {\log n}:$$n \log \frac{n}{\...

2

Each $j$ contributes $1$ to all $K'(\sigma)_i$ with $j < i < \sigma_j$. Ideally you want a data structure that maintains a collection of $n$ counters $C_0, \dots, C_{n-1}$ under the following operations: Offset($j$, $\delta$): Given $j$ and $\delta$, add $\delta$ to each $C_i$ with $i \le j$. Evaluate($i$): Return the value of $C_i$ When $\sigma_j$ ...

9

Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets. You can compute all $n$ values $K(\sigma)_i$ in $O(n)$ time as follows. Maintain an array $A[0, \dots, n-1]$ where each entry $A[i]$ is initialized to $0$. Then, for each $j$, increment $A[\min\... 0 This sounds quite a bit like a job for sorting networks (a fixed network of rounds that compare two elements and swap them if out of order). 2 Your problem is solved in Kahn and Kim, Entropy and sorting. 0 I think I have a solution. It's totally symmetric with no coordination. Each arbiter runs the following algorithm to choose their comparisons. First, they consider evenly dividing n into k "sections" (e.g. section 1 is from 1 to n/k, section 2 is from n/k+1 to 2n/k, etc.). Then, they randomly choose one of k sections to focus on. Next, they use ... 1 Take a look at Bentley's Programming Pearls. Not specifically about efficiency, but most of the advice in it does have an important bearing on it. A classic (sadly out of print) is his Writing Efficient Programs. Relevant is also Kernighan and Pike's The Practice of Programming. But it is critical to design and write clean, understandable programs first. ... 0 For$n \ge 16$you have$k \ge \frac{n}{8} \ge 2$and you can write the following: $$\sum_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) \ge \frac{n-(k-2)}{k-(k-2)-1} > n-k \ge n - \frac{n}{8} = \frac{7}{8} \cdot n.$$ For$2 \le n<16$,$\frac{n}{2 \log_2 n} < \frac{16}{8} = 2$(notice that$\frac{n}{2 \log n}$is a monotonically increasing ... 3 First of all, when we reduce problem$A$to$B$in polynomial time, we display it by$A\le_p B$, it's means that complexity of any algorithm for solving problem$B$is at least hard as problem$A$. From this we act as follow: Suppose you are Given un-dircted weighted graph$G=(V,E,M,\omega)$with weight function$\omega:E\to \mathbb{R}$, and$k_1=k_2=M$. ... 1 Converting it into an iterative algorithm is somewhat vague and there could be many different ways to do it. One way could be the following: isqrt(n){ if (n==0){ return 0; } a = 1; b = a*a; while (true){ if (n < b){ return a-1; } else { b += 2*a+1; a += 1; } } } Other options can be applying Newton's ... 2 Let$\langle S, t\rangle$be an instance of subset sum, where$S = \{x_1, \dots, x_n\}$, and$t, x_1, \dots, x_n \in \mathbb{N}^+$. Create a graph$G = (V,E)$where$V = \{u,v\} \cup S$and$E$contains: The edge$(u,v)$of weight$0$. For each$x_i \in S$, an edge$(u, x_i)$of weight$x_i$. For each$x_i \in S$, an edge$(v, x_i)$of weight$0$. ... 1 Try to think what happens when$k_1=k_2$. It makes the question much more difficult. In fact, consider the following reduction from subset sum: Say we have a set of numbers$S=\{a_1,\dots,a_n\}$and a target value$t$. Let us choose$k_1=k_2=t$, and build the following graph$G$:$G$will have$n+1$nodes: a special node will be called$v$, and another node$...

2

The second approach is technically the correct interperation. When we say "a verifier gets a certificate $c$ that looks like [...] and computes something", then we actually mean that this verifier checks whether $c$ is of the required format (e.g, check that $c$ is representing a subset of nodes from the graph), and if it isn't it will immediately ...

0

For this setting of parameters, I don't believe any method with better time complexity is known in the research literature.

2

It is theta of $2^{2n}$: $$2^{2n+2}=4\cdot 2^{2n}=\Theta(2^{2n})$$

0

It means we try to express the time needed to solve a problem as a function of the problem size, so that we know how to deal with larger problem sizes & scalability issues For example if we find it is linear in the problem size (T(n)=an+b) that's probably cool, if n=1000 or even n=10⁹ we can manage (our program will end its run in a acceptable time) ...

5

This is just an example. Easiest to think of an algorithm that has two nested loops over an array of size $n$ (e.g. Bubble Sort). You are correct. Again, if you think of an algorithm that has two nested loops and within the inner loop just one (or constantly many) operation $op$, then $op$ gets executed $n^2$ times. If you array has size 8, $op$ gets ...

Top 50 recent answers are included