# Tagged Questions

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

22 views

### Determing stretching variable in inner expansion of boundary layer problem

I am studying perturbation theory, and I have a problem when reading the book "Introduction to Perturbation Methods" by M.H. Holmes. This is about boundary layer. We know when seeking inner expansion, ...
33 views

### Limit of monotone decreasing function on generalised inverse.

Consider a right-continuous, monotone decreasing, non-negative function $\bar F(x)$ (its the tail of a probability distribution, but that doesn't matter). Now let I_{n}=\{x : \bar F(x)...
17 views

33 views

29 views

### Average of numbers converges, then what happens to the maximum

Let $\{a_n\}$ be a positive sequence of numbers such that $\displaystyle \frac1n\sum_{i=1}^n a_i \to a$ where $a>0$. Then can we say anything about the order of $\displaystyle b_n=\max_{i\in n} a_i$...
42 views

### 10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
36 views

### More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
60 views

### Asymptotic behavior of integrals of Legendre polynomials

By definition $\int_{-1}^1 |P_n(x)|^2 dx = O(n^{-1})$. What about the other powers? Do we know how $\int_{-1}^1 |P_n(x)|^k dx$ behaves for any $k$? Maybe $O(n^{-k/2})$?
33 views

### Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
31 views

24 views

### Linear combination of asymptotic series

I need to compute an expression of the form $$J=\sum_{k=0}^N a_k F_k(z)$$ where z is a large parameter, and a_k are easily computable (k and z-dependent) coefficients. I ...
42 views

Consider the system $$\varepsilon \dfrac{dx}{dt} = -(x^3 - ax + b)$$ $$\dfrac{db}{dt} = x - x_a$$ where $\varepsilon \ll 1$. Applying regular perturbation methods isn't suitable because when $\... 1answer 26 views ### Big O notaion O(n) and logaritms [closed] Can someone explain me the subjects Big O notation and logarithms please? I can't understand those subjects For example if I have a question like this: recall that logan is the power to which you ... 0answers 22 views ### Finding asymptotycs of partition function I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ... 1answer 47 views ### Verifying a step in the prime number theorem This is an excerpt from Shapiro, "Introduction to the theory of numbers": Suppose that we have an estimate of the form $$|R(x)|\le \alpha x$$ valid for all sufficiently large$x$(say$x\ge x_2$). ... 0answers 21 views ### Asymptotic upper bound for recurrence relations The question is to find asymptotic upper bound for recurrence: (1)$T(n)=(T(n/2))^2$and (2)$T(n)=(T(\sqrt{n}))^2$with$T(n) = \text{n for n} \leq 2$I think I will be able to find the ... 1answer 33 views ### Asymptotic upper bound$T(n)=(T(n−1))^2$The question is to find asymptotic upper bound for recurrence:$T(n)=(T(n−1))^2T(n) = \text{n for n} \leq 2$My attempt: I've tried to use substitution method and getting:$T(n) = ...
In my class, we have defined that $$f(x) \ll g(x)$$ on $A$ if there exist a strictly positive c such that $$|f(x)| \le cg(x)$$ for every $x$ on $A$. I'm a bit confused. Say that $f(x) = x$ ...
### Prove that the value of the constant $C$ must be $1$
After proving the prime number theorem in class, our professor directs us to a remark by Lagrange that for large values of $x$, $\pi(x)$ is approximately equal to $$\frac{x}{\log x - B}.$$ (This is ...