# Tag Info

0


0

Let $c = \frac{1}{2}$ and $k = 0$. Then $f(n) = n^{2} \geq \frac{1}{2} \cdot 2n^{2}$ for all $n \geq 0$. Since $\frac{1}{2} \cdot 2n^{2} = f(n)$, this proves the result.

-1

I have an idea. Try this, let $w^x = z$ then subtitutes to have $z^2 + z + 1 = x$ then use the quadratic formula to get the value of $z$ then plug it back to see what you got.

1

In parametrized algorithms, the algorithm gets an input $x$ and a parameter $k$. The usual usage of $O^*(f(k))$ is saying there exists an algorithm which runs in time $$O(f(k)\cdot \text{poly}(|x|))$$ (e.g. $O^*(2^{2^k})$ means the algorithm is allowed to run in $O(2^{2^k}|x|^6)$, but not in $O(2^{2^k+k}+|x|)$) This is somewhat different from the ...

1

The sum on $k$ just equals the constant times the number of terms. Assuming the integer square root, $$S= \sum\limits_{i=1}^N \sum\limits_{j=1}^i \sum\limits_{k=1}^{i\lfloor\sqrt{j}\rfloor}C = \sum\limits_{i=1}^N \sum\limits_{j=1}^i Ci\lfloor\sqrt{j}\rfloor = C\sum\limits_{i=1}^N i\sum\limits_{j=1}^i\lfloor\sqrt{j}\rfloor.$$ The sum on $j$ is uneasy and can ...

1

The sum of the submatrice consisting of rows $i_1$ through $i_2$ and columns $j_1$ through $j_2$ is basically $$(\sum_{i=i_1}^{i_2} A[i]) \times (\sum_{j=j_1}^{j_2} A[j])$$ From this property, we can construct an $O(N+K)$ solution (there are many alternative solutions, of course, for example, we can also do this in $O(d(K) N)$). Edit: OP asked how to do ...

1

The coefficient of $x^n$ is called the Hilbert polynomial. It can be calculated, see the book R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. (1999). See the Theorem 4.1.1 and Proposition 4.1.1 of the book. Related sofware see here I sure those calculation can be ...

0

If $n$ is size of input, and $T_n$ the time it takes. Super linear time means faster than any $C\cdot n$, i.e. $\limsup T_n/n=\infty$. Examples $T_n=n\ln(n)$, $n^2$, $n^n$ ... Sub linear time means slower than $n$, i.e. $\limsup T_n/n<\infty$. Examples $T_n=\sqrt{n}$, $\ln(n)$, ... $o(1)$ is something that tends to zero, $O(1)$ is something bounded ...

1

There are some missteps in your application of the master theorem. First $$T(n) = 7\left[ 7T\left(\frac{n}{4}\right) + \frac{1}{4}n^2\right] + n^2 = 49 T\left(\frac{n}{4}\right) + \frac{11}{4}n^2,$$ so let's call $a = 49$, $b = 4$, and $f(n) = \frac{11}{4}n^2$. Clearly $f(n) \in O(n^2)$, so let's also call $c = 2$. Then 2 = c < \log_b a = ... 0 Some possible answers include Machine learning: Machine learning is more or less applied statistics, using theoretical ideas from statistics to generate algorithms for analysing and grouping data. Data mining is also related to this area. Computer algebra: Computer algebra studies how to devise efficient algorithms for algebraic manipulations. Many ... 3 A simple way to determine runtime is to use summations. Each loop becomes a sum, where the lower index is the starting value of the loop and the upper index is the ending value of the loop. Because you're performing a constant time operation in the innermost loop, we are simply summing 1: \begin{align}\sum_{i=4}^{n^2} \sum_{j=5}^{3i\lg i} 1 &= ... 0 Remember that for every polynomial p(x)p(x)=\sum \frac{f^{(\alpha)}(0)}{\alpha!}x^\alpha Here $x=(x_1,x_2,...,x_n)$, $\alpha=(\alpha_1,\alpha_2,...,\alpha_n)$, $f^{(\alpha)}=\frac{\partial^{\alpha_1+...+\alpha_n}}{\partial x_1^{\alpha_1}...\partial x_n^{\alpha_n}}f$, $x^{\alpha}=x_1^{\alpha_1}...x_n^{\alpha_n}$, and $\alpha!=\alpha_1!...\alpha_n!$. ...

2

The value of $n$ considered in this problem when evaluating its time complexity is not the number itself, but rather the number of bits (equivalently, digits) the number has. When measured in that metric, the algorithm takes exponential time.

Top 50 recent answers are included