# Tag Info

0

Using Master's Method case 2 is applicable since $n^{\log_b a}=n^{\log_2 1}=1$ which is equal to $\theta(1)$. Thus from Master's method $T(n)=\theta(n^{\log_2 1}\log n) = \theta(\log n)$

0

If $A$ and $B$ are in $\mathtt{P}$ then they are equivalent, so there is no need to reduce one to the other. Similarly all problems in $\mathtt{NP}$ are equivalent. So if we (in this case) reduce a problem in $\mathtt{NP}$ to one in $\mathtt{P}$, then all problems in $\mathtt{NP}$ follow suit.

0

Assuming inside of third loop takes constant time $c$ then running the whole algorithm takes: $$T(n) = \sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} \sum_ {k = j} ^ {2 j} c$$ Summation limits are exactly same as in the loops. We can then calculate $T(n)$ : \begin{aligned} T(n) &= c\sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} (2j - j + 1) \\ \\ & \vdots ... 0 For \theta(n) of the time of the first loop, i is \theta(n). (Think about the second half of this loop when i>\frac{n}{2}.) In this time, for \theta(i)=\theta(n) of the time of the second loop, j is \theta(i)=\theta(n). In this time, for \theta(j)=\theta(i)=\theta(n) of the time of the second loop, k is \theta(j)=\theta(i)=\theta(n). ... 11 Cramer is highly inefficient, of time complexity O(n! \times n) with a naive determinant-finding algorithm, and O(n^4) with e.g. LU decomposition. Gaussian elimination has cubic complexity. 3 Reducing the matrix to triangular form and multiplying the elements on the diagonal is usually quicker. I am pretty sure that is the algorithm most computer algebra systems use, unless it is known in advance that the matrix has some special properties. Sometimes Laplace expansion can be quicker if the matrix has many zeros along some rows/columns. 0 Let n = 2^y Therefore \log_2(n) = y LHS = \sqrt{2}^{\log (n)} = \sqrt {2}^y = 2^{\frac{y}{2}} = \sqrt{n} RHS = n^{\log(\sqrt{2})} = \sqrt{n} = \sqrt{2^y} = 2^{\frac{y}{2}} = \sqrt{n} 0 \begin{align} \sqrt{2}^{\log_2 n}\qquad\qquad \text{Given Equation}\\ = 2^{\frac{1}{2}\log_2 n}\qquad\qquad\qquad \sqrt{n} = n^{\frac{1}{2}}\\ =2^{\log_2 \sqrt{n}}\;\;\qquad a\log_b n = \log_b n^a\\ = \sqrt{n}\qquad\qquad\qquad\quad b^{\log_b n} = n\\ \end{align} 0 We have \begin{align} \sqrt{2}^{\log_2 n}&=\left(2^{1/2}\right)^{\log_2 n}\\ &=2^{(1/2)\log_2 n}\\ &=2^{(\log_2 n)(1/2)}\\ &=\left(2^{\log_2 n}\right)^{\frac{1}{2}}\\ &=n^{\log_2 \sqrt{2}}\quad\text{since }\log_2\sqrt{2}=\frac{1}{2} \end{align} 2 Using the rule a=2^{\log_2 a}, we have \sqrt{2}^{\log_2 n}=2^{\log_2(\sqrt{2})\log_2 n}=n^{\log_2\sqrt{2}}. 1a^{\log b} = \left(2^{\log a}\right)^{\log b} = 2^{\log a \log b} = \left(2^{\log b}\right)^{\log a} = b^{\log a}$$If your log base is something other than 2, use that instead. 0 The first loop is over all odd integers less than n. The second loop is over all integers from 0 to i. There is one multiplication in the inner loop. This gives us that the total number of multiplications is$$2 + 4 + 6 + \ldots + 2\left\lfloor\frac{n}{2}\right\rfloor = 2\left(1+2+\ldots+\left\lfloor\frac{n}{2}\right\rfloor\right) = ...

0

Work it out from the inside summation. $\sum_{i=0}^7 \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^7 (n-1-i) = 8(n-1)-(0+\cdots+7)$.

0

Hint: As is often the case in math, you take it apart. The inner loop starts at $j=i+1$ and executes through $j=n-1$. How many values of $j$ is that? You are allowed to express it in terms of $i$ and $n$. Then you need to sum this expression over $i=0$ through $i=7$

0

Let's derive $T(n)$, the runtime function. The outer loop executes $n^{2}$ times, given by the summation: $$\sum_{i=0}^{n^{2} - 1}$$ The inner loop executes $i+1$ times given by the summation $\sum_{j=0}^{i}$. Each iteration of the inner loop operates in $O(1)$ time, which I will just denote as the constant $c$. So we have: $$T(n) = \sum_{i=0}^{n^{2} - 1} ... 0 Outer loop is executed n^2 times. Inner loop is executed 1, 2, \dots, n^2 + 1 times. Therefore, in total there are \frac{1}{2} (n^2 + 1)(n^2 + 2) floating point multiplications. 1 You don't really have the precise definition of \Theta notation. Given two functions f, g defined on \mathbb N, we say that f(n)\in\Theta(g(n) if there exist constants c, C and a positive integer n_0 such that n\geqslant n_0 implies that$$ cg(n) \leqslant f(n) \leqslant Cg(n).$$Since$$\max\{f(n),g(n)\} \leqslant f(n)+g(n) \leqslant ...

0

I think this is the solution. We know that $f(n) = \Theta(g(n))$ means $f(n) = O(g(n))$ and similarly $f(n) = \Omega(g(n))$ $m\{f,g\} = O(f+g)$ letting $c>0$ $f + g = O(m\{f,g\})$ letting $c \ge 2$ So basically without getting bogged in notation: $f = O(g)$ where $c >0$ Similarly: $g = O(f)$ where $c \ge 2$ which $\implies f = \Omega(g)$ ...

0

From the generalized binomial theorem, we have $$(n+a)^b = \sum_{k=0}^\infty\binom bk n^{b-k}a^k.$$ If $b$ is not an integer, we define $$\binom bk := \frac{(b)_k}{k!}$$ where $$(b)_k := \prod_{i=0}^{k-1} (r-i).$$ From this it follows that $$(n+a)^b = n^b + \Omega(n^{b-1}),$$ and hence $(n+a)^b \in\Theta(n^b)$.

0

Ahh, I just realized that they are both $O(n\log n)$ because the $n$ is not separate from the $\log n$ which makes them one term. So the solution in the book is in fact correct.

1

You are asking about the asymptotic behaviour of $$\sum_{k=1}^n k$$ as $n→∞$. We can write this as $$\sum_{k=1}^n k = \frac{n(n+1) }{2} = \frac{n^2}{2} +\mathcal{O}(n) = \mathcal{O}(n^2)$$ Doing it twice doubles the 'time taken'; this amounts to multiplying the $\mathcal{O}$ constant by 2, which is ok. That is, it is still $\mathcal{O}(n^2)$.

-1

You're right in assuming the smaller terms are of little relevance. $n + (n-1) + (n-2) + ...$ tends to $O(n^2)$ for sufficiently big $n$. As for $2(n + (n-1) + (n-2) + ...)$, simplify it the best you can, and know that a coefficient doesn't change how it tends. $2n + (2n-2) + (2n-4) + ...$ also tends to $O(n^2)$ for sufficiently big $n$.

1

In order to make the map $$f(x) = \sum_{i=1}^N a_i x_i$$ a bijection ($f(x)=n$ and $x = (a,b,c,d,e,f)$ in your OP) where $x_i$ can take the values $0$ to $M_i-1$ can be consructed by chosing $a_1 = 1$ and $$a_{i+1} = a_i M_i$$ Here you'd get $$f(a,b,c,d,e,f) = a + 5b + 25c + 100d + 400e + 1200f$$ The inverse is given by $$(f^{-1}(n))_i = (n \mathop{\rm div} ... 1 There are three places to put the 2 t(n^2) is unambiguously defined. t^2(n) could mean t(t(n)) or (t(n))^2, generally the author makes it clear which is meant. t(n)^2 is not very common but it always seems to mean (t(n))^2. 2 For some functions f^2(n) = f(n^2), for example f(n)=n. However, this is not true for all functions. Take for example: log(n). log^2(n) is not always equal to log(n^2) for all n. See the chart below: 1 Assuming you mean quadratic time (please correct me if I'm wrong - I'll fix my answer), I usually see it written t(n)=O(n^2). However, in your case, since t is a polynomial in terms of n, we are squaring the actual polynomial, and not the input value (n). t(n^2) and t^2(n) are different, for example, given the polynomial t(n)=n^2+1, we see that ... 1 If a function f is polynomially bounded,it means there exist a polynomial g and h such that for all x, g(x)<=f(x)<=h(x). 3 Every complexity class is really just a set of languages. For example, NSPACE(T(n)) is the set of all languages that are decidable by some non-deterministic Turing machine using space O(T(n)). So NTIME(T(n)) \subseteq NSPACE(T(n)) just means that for any language L, if it is decidable by some non-deterministic Turing machine using time O(T(n)), ... 1 This is true in the limit n \to 0^+. One very useful tool for problems like this is Taylor series. Hint: Write n+O(n^2) as n(1+O(n)), bring a \sqrt{n} outside of the square root, then try to use the binomial series. 2 Another hint: consider a series with the term a_n=n^{\log n}/n! and use, e.g., D'Alambert's test to find out that your series converges. Hence the common term of the series must tend to zero. 0 Using a multiplicative variant of Gauss's trick we have:$$ (n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n $$So$$ \dfrac{n^{\log n}}{n!} \le \dfrac{n^{\log n}}{n^{n/2}} \le \dfrac{n^{n/4}}{n^{n/2}} = \dfrac{1}{n^{n/4}} \to 0 $$because \log n \le n/4 for n ... 4 Hint: Since \log(n)\le \sqrt{n} for all n\ge N_0 for some positive integer N_0, we get that:$$\frac{n^{\log n}}{n!}=\frac{e^{(\log(n)^2)}}{n!}\le \frac{e^{n}}{n!}$$1 Hint: \log(ab) = \log(a)+ \log(b) 1 There are a bunch of teddy bears A, B, C, D and so on that are red on one side and blue on the other! (You choose how to color them) AND there are a bunch of 3 armed aliens with really long arms. Each alien grabs 3 teddy bear hands! (A teddy bear hand can be grabbed by more than one alien.) 3-SAT is the problem of whether you can color the teddy bears ... 0 If n = 2^m, this becomes T(2^n) =T(2^{n-1})+\log(2^n) =T(2^{n-1})+n\log(2) . Letting T(2^n) = s(n), we get s(n) = s(n-1)+n\log 2 . You should be able to solve this. Another way is to repeatedly apply the recurrence: \begin{array}\\ T(n) &= T(n/2)+\log(n)\\ &= T(n/4)+\log(n/2)+\log(n)\\ &= T(n/8)+\log(n/4)+\log(n/2)+\log(n)\\ ... 2 Split your polynomial into odd and even parts. The even part is$$f_E(x) = a_0 + a_2x^2 + a_4x^4 + \cdots$$which you can consider a polynomial in x^2 and evaluate by n/2 steps of Horner's method. The odd part is$$ f_O(x) = a_1x + a_3x^3+a_5x^5 + \cdots = x(a_1+a_3x^2 + a_5x^4+\cdots) $$where the bracket on the right is again a polynomial in x^2 ... 0 If you could accept non-exact value for the intersection volume, then you can try the famous Monte Carlo Method. Surround your two polyhedrons by an iso-oriented cube and generate uniformly distributed (in this cube) sample points - for each point you can quickly verify if it's inside the intersection or not. Calculate two numbers - the number of all ... 1 We don't throw out constants. See, suppose we have O(n^2); now what is that little figure 2? A variable? Definitely not. A constant? Surely! Can't we just throw it away? We may throw out additive constants, but that's another story. 8 Look at the ratio:$$\lim_{n\to\infty}\frac{n\cdot n!}{n!}=\lim_{n\to\infty}n=\infty\;,$$so n\cdot n! cannot be O(n!). 1 Good thinking. The answer lies in the definition of a communication protocol on p. 192. The definition says that it's determined by the communication protocol which player communicates next, depending only on the communication pattern of the previous rounds and not on the players' inputs. So the idea is that the players communicate one bit at a time, and ... 0$$ \sum_{i=0}^n (2i^3 + 4i^2 + 2) = 2\left( \sum_{i=0}^n i^3 \right) + 4\left( \sum_{i=0}^n i^2 \right) + 2\left( \sum_{i=0}^n 2 \right). $$Therefore, it is enough to deal with each of \displaystyle\sum_{i=0}^n i^k for k=0,1,2,3,\ldots. For that we need the Bernoulli polynomials B_n, characterized by$$ \int_x^{x+1} B_n(u)\,du = x^n. $$We have$$ ...

1

As discussed in the comments, here's a solution to the problem without the restriction to odd sums. If a sequence is minimally good, we cannot reduce any of the $a_i$, so there must be at least one sum that exactly equals $k$. Then the element not included in that sum must equal the greatest element included in the sum: If it were greater, we could reduce ...

Top 50 recent answers are included