# Tagged Questions

Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

26 views

### Richardson extrapolation for set of points

I have a boundary element method code which gives me the numerical solution of a problem. The finer mesh I use, the more exact will be the answer. So I have a set of points as my answers. I want to ...
54 views

63 views

### Asymptotics of the solution of $G_n(t) = \text{const}$, where $G_n(t) = e^t (1 + r^{-1}(G_{n-1}(t) - 1))^{r}$.

Consider a sequence of functions $(G_n(t))$ on $\Bbb{R}$ that satisfies the recurrence relation $$G_0(t) = e^t, \qquad G_n(t) = e^t \left( 1 + \frac{G_{s-1}(t) - 1}{r} \right)^{r}.$$ for some ...
50 views

59 views

23 views

### Questions about $w(\prod_{k=1}^{n}(p_{k}-1))-w(\prod_{k=1}^{n}(p_{k}+1))$

Let's define this functions. $$f(n)=\prod_{k=1}^{n}(p_{k}-1)$$ $$g(n)=\prod_{k=1}^{n}(p_{k}+1)$$ $$h(n)=\mid w(f(n))-w(g(n))\mid$$ where $p_{k}$ is $k$th prime number and $w(n)$ gives the number of ...
42 views

### Errors in our estimation of a function- and what does big-O notation have to do with it?

We're given the function $f(x) =e^x$ and we're trying to estimate its second derivative at $x=0$. Here's the estimation formula. $$f''(x)\approx {f(x) - 2f(x+h) + f(x+2h)\over h^2}= P(x)$$ All three ...
29 views

### How many binary polynomials of degree <2n-1 are the the product of polynomials of degree <n?

Let $P_n$ be the set of all polynomials over $\mathbb{Z}_2$ and of degree less than $n$. What is the rate of growth of $|\{x y : x,y \in P_n \}|$? I'm looking for an answer like "$\Theta(2^{3n/2})$" ...
43 views

### Big O - equivalent definitions

A function $f(x)$ is $O(g(x))$ if and only if there exists a real number $M$ such that there exists $x_0$ such that for every $x>x_0$ the inequality $|f(x)|\le M|g(x)|$. It turns out the following ...
164 views

128 views

### Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
40 views

### Book Recommendations on Perturbation Theory

I am interested in studying Quantum Electrodynamics and figure I should begin by learning Perturbation theory and Asymptotic expansions. If anyone could recommend some books, that would be very ...
52 views

### Can I say $\log{O(n)}$?

Suppose $e^{f(x)} = O(x)$, or equivalently, there exists a $c$ such that for all $x$, $f(x) \lt \ \log{x} + c$. Is $f(x) = \log{O(x)}$ generally understood to mean the same thing?
45 views

20 views

### Big-O Notation and showing algorithmic growth rate with witnesses?

I have been out of class sick for a week with the flu and am having some trouble getting caught up on our latest sections on Big-O notation. Can someone explain the following from the textbook to me? ...
Suppose we generate "random strings" over an $m$-letter alphabet, and look for the first occurrence of $k$ consecutive identical digits. I was with some effort able to find that the random variable ...
In Iwaniec's book, Topics in Classical Automorphic Forms, pg. 4, he gives the statement: $$\{x\}=\frac{1}{2}-\sum_{n=1}^N\frac{\sin 2\pi nx}{\pi n}+O((1+||x||N)^{-1})$$ where $\{x\}$ denotes the ...