Tag Info

New answers tagged

0

You are correct. The last line should read $$ \sum_{i=0}^{N-1} (N - i -1). $$ The next line of the slide also has an error: rather than $$ N\sum_{i=0}^{N-1} 1 - \sum_{i=0}^{N-1} i, $$ it should read $$ N\sum_{i=0}^{N-1} 1 - \sum_{i=0}^{N-1} (i + 1) \qquad \text{or} \qquad N\sum_{i=0}^{N-1} 1 - \sum_{i=1}^{N} i $$ and the concluding equality should be $$ ...


0

For a discriminant to be a perfect square you need $k^2 + 2m + 1 = n^2$, that is $2m + 1 = (n+k)(n-k)$. In other words, factorize $2m + 1$; for each divisor $d < \sqrt{2m + 1}$ there is a solution $k = \frac{\frac{2m + 1}{d} - d}{2}$. It is still $O(\sqrt{2m})$ loop, but instead of testing a quadratic you only need to test for divisibility.


0

you can solve the quadratic equation in α. For integer solutions, we must have k^2 + 2m +1 = a perfect square. You then have a solution when k=m since then k^2 + 2k + 1 = (k+1)^2.


0

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} ...


2

Calculating the first few values: $0,5,20,65,200$ , dividing by $5$ this is $0,1,4,13,40$ , multiplying by $2$ we get $0,2,8,26,80$ adding $1$ we get $1,3,9,27,81$. Otherwise you can use generating functions: Let $A=\sum\limits_{n=0}^\infty t(n)x^n$. Then $A=3xA+5\sum\limits_{n=1}^\infty x^n$ (since $f(0)=0$). Then $(1-3x)A=\frac{5}{1-x}-5$ so ...


1

There are two types of solutions here: the homogeneous and the particular. Rewrite the equation as $$T_n - 3 T_{n-1} = 5$$ The homogeneous solution is simply the solution assuming the RHS is zero. Thus $T_n^{(H)} = A \cdot 3^n$. The particular solution is a simple solution that satisfies the equation and boundary conditions. In this case, $T_n^{(P)} = ...


1

$$\lim_{n \to +\infty} \frac{g(n)}{f(n)}=c$$ means that $\forall \epsilon>0, \exists n_0 \in \mathbb{N}$ such that $\forall n \geq n_0:$ $$\left |\frac{g(n)}{f(n)}-c \right | < \epsilon \Rightarrow - \epsilon< \frac{g(n)}{f(n)}-c< \epsilon \Rightarrow c- \epsilon< \frac{g(n)}{f(n)}<c+\epsilon \\ \Rightarrow (c-\epsilon)f(n)< ...


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