New answers tagged

0

In general, if I can enumerate a list of computable functions I know to be total, then I can enumerate that same list without repetition. Here's how to do this. Suppose I have an enumeration $\{f_n: n\in\mathbb{N}\}$ of some total computable functions. Say $f_n$ looks new at stage $s$ if for every $m<n$, there is a $k<s$ such that ...


2

You are correct. There might be an $NP$-complete problem that can only be translated into Hamiltonian path problem in $\Omega(n^{10})$ time, for instance. In which case an $\Omega(n^{10})$ translation and an $O(n^4)$ solution gives a total time of $\Omega(n^{10})$. The only thing you can be certain of is that the final time is bounded by a polynomial.


1

If you write your algorithm out in English, it is something like the following: while the number is not 1, try dividing it by every number in order, beginning with 1. Every time we find a factor, divide the original number by the factor, then continue on. To take 187 as an example, you first try all divisors less than 11 unsuccessfully, then find that 11 is ...


1

I would leave a comment but don't have the reputation: check out http://www.math.udel.edu/~lazebnik/papers/dioph2.pdf, which also looks to have several useful references (in particular http://www.math.tamu.edu/~rojas/kannanbachemhermitesmith79.pdf for algorithms to compute Smith normal form).


0

Here's a start on improving the $81^{16}$ upper bound. The total number of ways that gobblets can be placed on the board is no more than $$\left({16\choose0}+2{16\choose1}+4{16\choose2}+8{16\choose3}+14{16\choose4}+20{16\choose5}+20{16\choose6}\right)^4\\=277{,}993^4\approx5.97\times10^{21}$$ That is, a state of the board is determined by specifying, for ...


0

Let $B$ be a language in NP and co-NP. If B is also in NP-Complete then NP = co-NP. To prove that, we need to prove: $A \in NP \iff A \in$ co-NP $A \in NP$ $\Rightarrow A <_p B$ $\quad\quad$(since $B \in$ NP-Complete) $\Rightarrow \bar A <_p \bar B$ $\Rightarrow \bar A \in NP \quad\;\;$ (since the NTM for $\bar B$ is also an NTM for $\bar A$) ...


1

Since $\log_an=(\lg_ab)(\log_bn)$, you have that $\log_an$ is just a constant multiple of $\log_bn$, and we know that constant multiples are invisible to asymptotic estimates.


0

I assume that by "complexity" you mean the value. In Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$ I showed that for $n \ge 2$, $$\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n \text{ where } r_k = \frac{k^k}{(k-1)^{k-1}} $$ and, if you use Stirling's formula, you get $$\binom{kn}{n} \approx ...


0

In this particular case, the base doesn't matter. $$n\log_b(\log_b(n))=n\frac{\ln\left(\dfrac{\ln(n)}{\ln(b)}\right)}{\ln(b)}=n\frac{\ln(\ln(n))-\ln(\ln(b))}{\ln(b)}=O(n\ln(\ln(n)))$$ as the second term is of a lower order.


0

Big $O$ complexity in terms of nested logarithms is base independent for the same reason it is in the case of single logarithms. For example, $\log_{10} x = c \log_2 x$ for the constant $c=\log_{10} 2$, as you have noted. Likewise, using a specific example, $\log_{10} \log_{10} x = d \log_2 \log_2 x$ for some $d$ that approaches (but does not equal) ...


1

$$ \lim_{n\to \infty} \frac{(n+1)!}{n!}=\lim_{n\to \infty} (n+1) = +\infty$$ which implies $(n+1)!$ is not $O(n!)$.


2

If it helps, think of $\mathbb{Z}[X_1,X_2,X_3] $ as $\mathbb{Z}[x,y,z]$ and then your favorite polynomials (in three variables) from multivariable calculus are in this ring. For instance, for $z^2=x^2+y^2$, you have $z^2-x^2-y^2 \in \mathbb{Z}[x,y,z]$. But for an arbitrary polynomial in $m$ variables it is better to write $X_1,...,X_m$ than choosing $m$ ...


2

This means that $p$ is a polynomial with integer coefficients in $m$ variables. An example would be $$ p( X_1 , X_2 , \ldots , X_m) = X_1 + X_2 + \cdots + X_m. $$


0

With the Sieve of Eratosthenes, $\log$ refers to $\ln$ and is due to the nature of the sieve and its relationship to the Prime number theorem $\pi(N) \sim N/\ln N$. (Computational analysis from wikipedia)


0

Step by step : $\frac {2n^{14} + 7 n^8 -3} {3n^8 - n^4 + 3}=\frac {n^{14}} {n^8}\frac {2 + 7 n^{-6} -3n^{-14}} {3 - n^{-4} + 3n^{-8}}$ When $n\longrightarrow \infty$, the right side fraction has finite limit $\frac 2 3$, so it is bounded. Let $B\in\mathbb R$ be this bound. $\frac {2n^{14} + 7 n^8 -3} {3n^8 - n^4 + 3}=n^{6}\frac {2 + 7 n^{-6} -3n^{-14}} {3 ...


1

Since $$\frac{2n^{14}+7n^8-3}{3n^8-n^4+3}=\frac{2n^6+7-\frac{3}{n^8}}{3-\frac{1}{n^4}+\frac{3}{n^8}}$$ it will be a $O(n^6)$.


1

It is usually enough to show that $\frac{f}{g} \to_n 0$ to show $o(▪)$


0

Consider, for $x\ge1$ $$|f(x)|=|a_ix^i+a_{i-1}x^{i-1}+\cdots a_0|\le|a_i|x^i+|a_{i-1}|x^{i-1}+\cdots |a_0|\\ \le|a_i|x^i+|a_{i-1}|x^i+\cdots|a_0|x^i$$ as $x^i\ge x^{i-1}\ge\cdots x^0$. Then you have $$C=|a_i|+|a_{i-1}|+\cdots|a_0|.$$


2

We know that $N$ has a factor $p$ between $0.97213\sqrt N$ and $0.97476\sqrt N$. Then for suitable $a$ (small, but with good factors), $N'=aN$ may have a factor very close to $\sqrt{N'}$, and that can be found by Fermat's method. For example if $a=20\cdot 19$ and $p\approx 0.97476\sqrt N$ then $20p\approx 1.00008\sqrt{aN}$. This $a$ was just a simple ad hoc ...


0

As $f_A(n)$ and $f_B(n)$ denote the worst case time complexity, the first statement does not allow any conclusions on $f_A(n)$ and $f_B(n)$. It might be the case that $x$ is the easiest input for algorithm $A$ (i.e., $A$ is fast on $x$) and the hardest input for algorithm $B$ (i.e., $B$ is slow on $x$) or vice versa. This said, it is possible that $f_B(n) = ...


1

For any polynomial $$P(x)=\sum_{k=0}^d p_kx^k$$ and $x>0$, we have $$\frac{P(x)}{x^d}=\sum_{k=0}^d\frac{p_k}{x^{d-k}}=p_d+\frac{p_{d-1}}x+\frac{p_{d-2}}{x^2}+\cdots\frac{p_0}{x^d}.$$ Then if $p_d>0$, we can find an $x$ large enough such that $$-\frac{p_d}d<\frac{p_{d-1}}x,\frac{p_{d-2}}{x^2},\cdots\frac{p_0}{x^d}<\frac{p_d}d,$$ for instance ...


0

Let us assume you are interested in positive $n$. Since there are explicit negative signs, I also assume the $b_k \ge 0$. Now set: $$ n_0 = \max \left(\frac{3b_{k-1}}{b_k}, \sqrt[k-1]{3\frac{b_{0}}{b_k}},1\right)\,.$$ They relate to the second monomial, the last one, and the $1$ avoids divisions by zero. Basically, the $3$ factors are meant to end up with ...


0

Consider $\mathcal{F} = \{n \mapsto n^\alpha \,\mid\, 0<\alpha < 1\}$. Assume that your conclusion holds, i.e. there is $g \in S = S_{\mathcal{F}}$ such that for every $h \in S$, we have $g \in O(h)$. Consider $h_n := g_n / \ln n$ (here, I ignore the requirement $h_n \in \Bbb{N}$, this can be fixed by rounding, I omit the details). Let $\alpha \in ...


2

The algorithm used by the mldivide operator is descried here in Matlab's documentation: http://www.mathworks.com/help/matlab/ref/mldivide.html The "general" backslash for square matrices would end up using LU decomposition, while for symmetric matrices the Cholesky decomposition is used instead. This decomposition, which is simply a simplification of LU for ...


0

The computational complexity is going to be the same either way (in the typical big O notation). Whenever you are talking about doing something once or twice (or a fixed $n$ number of times), or on double or single length input, you are just talking about the constant factor, not the argument, associated with big O complexity. So, what you are talking about ...


1

Your range has an upper bound about 2-3 percent larger than the lower bound. So, the answer is that there is nothing much you can do simply based on a range like that. This is because you could start with a small range, say 100-102. Then 102-102*1.02, then 102*1.02-102*1.02^2, and so forth. Proceeding like that, you only need about log base 1.02 of $n$ steps ...


2

It is enough to take $t^* = e(d+1)!/\epsilon^{d+1}$. Proof: The LHS of the desired inequality is at most $t^d/0! + t^d/1! + \cdots t^d/d! \le et^d$ (assuming $t\ge 1$ which is fine). The RHS of the desired inequality is at least $(\epsilon t)^0/0! + \cdots + (\epsilon t)^{d+1}/(d+1)! \ge (\epsilon t)^{d+1}/(d+1)!$. Therefore, it is enough if we ensure ...


2

In general there is no such closed-form expression, but closed-form bounds are possible. EDIT: Of course if $\epsilon \ge 1$, the inequality is true for all $t \ge 0$, so consider the case $0 < \epsilon < 1$. I'll denote the left side as $M_d(t)$. We can consider this as $e^{t} \mathbb P[X \le d]$, where $X$ is a random variable having Poisson ...



Top 50 recent answers are included