2

See Simon Plouffe's Inverse Symbolic Calculator and Robert Munafo's RIES - Find Algebraic Equations, Given Their Solution.


2

I think you can get $O(\log n)$ by making every node store the number of nodes and the sum of all beneath it. Inserting/deleting one node changes $\log n$ nodes above it, and a tree-rotation at balancing time only requires recomputation of one nodes from its children (the other node just copy what was already there), so it doesn't hurt our $O(\log n)$ ...


2

With $T(n)=C+2n(\log(n)-\log(2))$, we have $$\begin{multline*}T(2n)=C+4n(\log(2n)-\log(2))=C+4n\log(n)=\\ C+2n(2\log(n)-\log(2n))+2n\log(2n)=C+2n(\log(n)-\log(2))+2n\log(2n)\end{multline*}$$ though J.G.'s answer provides an actual strategy for coming up with plausible forms for $T(n)\hspace{-3em}-\hspace{-.4em}-\hspace{-.4em}-\hspace{-.4em}-$ besides "...


2

Some useful information The integral converges if $a>1$ and $p>1/2$. The integrand is decreasing rapidly. We will only have to look at a few small values. We define the integral $$I(a,p)=\int\limits_{a}^{\infty}\frac{1}{(x^2-1)^p}\,\mathrm{d}x.$$ For big $p$ In this graph we set $p=50$. You can see that the values are very small. The spike at $3$ ...


2

The second formula is simply a rearrangement of the first, and what you're calling "factor" should simply be the number of observations. Setting the factor equal to $20$ forever instead is just a way of weighting new observations more heavily than old ones, which I take it is not what you want. Let the old mean be $\mu$, the new observation be $x$, ...


1

It seems that you have struggles with understanding what Big-O means in the first place, so I've decided to add some further details, although the comments and the already given answer are sufficient. The Big-O notation was first introduced by Paul Bachmann in "Analytische Zahlentheorie (1894)" for a way of expressing approximation. On page $401$ ...


1

You have: $\begin{align*} n^3 / 3 + 6 n^2 - 10000 &= O(n^3) \\ 5 n \log 2 n + 6 n &= O(n \log n) \end{align*}$ You prove the above and take it from here.


1

For integer values of $p$, there are very nica patterns for $$I_p=\int\limits_{a}^{\infty}\frac{dx}{(x^2-1)^p}$$ We have $$I_p=\frac {a\, J_p}{2^{p-1}\, (p-1)!\,(a^2-1)^{p-1}} +(-1)^{p+1}\, 4^{1-p}\, \binom{2 p-2}{p-1}\,\coth ^{-1}(a)$$ where $J_p$ represents a polynomial of degree $(p-2)$ in $a^2$. The first of these are $$\left( \begin{array}{cc} p & ...


1

Suppose that your original algorithm had complexity $O(N)$. Like, the brute force method requires $N=n!$ with $n$ the number of destinations. Then depending on at which of your checks you find the minimum, it could be the 1st, 2nd, third check, ..., all the way to the last one. On average, you will need $\frac{1+2+...+n!}{n!}=\frac{n!(n!+1)}{2n!}=\frac{n!+1}{...


1

In the worst case, it is as difficult as the original problem without the hint. For example, suppose that all weights are $1$, and I tell you that the shortest tour has length $n$, where $n$ is the number of nodes.


1

The outer $\texttt{for}$ loop for i := 1 to m do amounts to \begin{align*} 2\sum_{i=1}^m 1+2=2m+2 \end{align*} operations. The inner $\texttt{for}$ loop for j := i+1 to n do amounts to \begin{align*} 2\sum_{j=i+1}^n 1+2&=2\sum_{j=1}^{n-i} 1+2\\ &=2(n-i)+2=2(n-i+1)\tag{1} \end{align*} operations. Both $\texttt{for}$ loops for i := 1 to m do ...


1

The Ansatz $T(n)\sim An^c\ln^kn$ gives$$n\ln n=T(n)-T(n/2)=An^c\ln^k n-A2^{-c}n^c(\ln n-\ln 2)^k.$$If $c\ne0$ the RHS is asymptotic to $An^c\ln^2\ln^{k-1}n$ so $c=1$, a contradiction. So $c\ne0$ and $A=\frac{1}{1-2^{-c}}$. By inspection $A=2,\,c=k=1$ works.


1

One way is to find, on $n \in [1,\infty)$, the minimum and maximum of $$ \frac{n^2 -3n + 2}{n^2} \text{.} $$ Let $\ell$ be the global minimum and $u$ be the global maximum. Then you know $$ \ell n^2 \leq n^2 - 3n + 2 \leq u n^2 \text{,} $$ where $\ell$ and $u$ are constants (independent of $n$). This establishes the result you want. In this ...


1

You might explore Ries, specifically about the Ries algorithm.


1

It looks like OP is looking for an algorithm to find a perpendicular vector. Let $\mathbf{p}_1 = (x, y, z)$ be the original unit vector, $x^2 + y^2 + z^2 = 1$. I shall use notation $$\mathbf{p}_1 = (x, y, z) = \left[\begin{matrix}x\\y\\z\\ \end{matrix}\right]$$ where the parenthesised form $(x, y, z)$ is just shorthand for the proper vector/matrix form. ...


1

If $p\in\mathbb{C}$ one could use the extended binomial series $$(x^2-1)^{p} =\sum_{k=0}^{\infty}\binom{p}{k}x^{2(\alpha - k)}(-1)^{k}\quad (2)$$ to split the integral up. This series converges for all $x\in \mathbb {R}$ with $x>0$ and $\left|{\tfrac {1}{x}}\right|<1.$ The binomial coefficient is defined for complex values as $$\binom\alpha z=\frac{1}{(...


1

Note that whenever $x$ and $y$ are positive integers, $$ \binom{2(x+y)}2> \binom{2x}2+\binom{2y}2 $$ Therefore, if you have a vector $(x_1,\dots,x_n)$ where there are two nonzero components, then you get a larger value of $\sum_i \binom{2x_i}2$ by combining those two nonzero components into one. This means that the vector which attains the optimum must ...


Only top voted, non community-wiki answers of a minimum length are eligible