# Tagged Questions

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

19 views

### Proving equation using formal O(f(n)) - step by step?

I have huge problems showing whether example like this: is true or false using formal definition of Big O. How can I solve such problems step by step? I understand that formal definition of O(f(...
35 views

30 views

### Why is $O(x^{\alpha + \epsilon}) \neq O(x^{\alpha})$ if $\epsilon$ is arbitrarily small but greater than $0$?

There are several equivalent formulations of the Riemann hypotheses that utilize the big O notation. For example, it is known that $M(x) = O\left(x^{\frac12+\epsilon}\right)$ for all $\epsilon > 0$,...
48 views

### Finding the real part of a complex function

I am trying to compute the real part of the following complex function: $$S(z) = \frac{8}{3}\sqrt{z^{-\frac{1}{2}} + z^{-1}}\left(z + z^{\frac{1}{2}}\right)$$ For context, this expression was ...
62 views

### Asymptotic behaviour of the integral

Suppose I have the integral $$\tag 1 I\left[p\equiv -\frac{1}{2}\pm ia, z\right] \equiv \frac{1}{\Gamma(-p)}\int \limits_{0}^{\infty}e^{-xz -\frac{x^{2}}{2}}x^{-p-1}dx$$ I'm interested in asymptotic ...
27 views

### Lagerstrom-Cole equation

Consider this boundary value problem $$\epsilon u''+uu'-u=0,\quad u(0)=A\in\mathbb{R},\quad u(1)=3.$$ This differential equation is known as Lagerstrom-Cole equation. I trying to construct asymptotic ...
16 views

### Why asymptotic notation trying to get rid off multiplicative constants?

When I reading through an article about asymptotic notation, there is a sentence - "For large enough inputs, the multiplicative constants and lower-order terms of an exact running time are dominated ...
44 views

### Is it true $2^{2^n} = O(2 ^n )$?

I have some problem to solve this question. Intuitively, I think not, but I'm not sure. If a log the lelf a have $2^n \log2 <= 2^n$ That's ok ?
47 views

12 views

16 views

### Singular Perturbation Asymptotic Expansion

In the question above, for the outer solution, how do I express the RHS? The question only asks for O(1), but I can express the RHS as (U0 + (U0)^2) * (sum of infinite series of O(1)), where the ...
30 views

### if f and g are monotonically increasing functions, such that f(g(n))=O(n) and f(n)=Ω(n) then g(n)=O(n) [closed]

I have to prove this statement : if $f$ and $g$ are monotonically increasing functions, such that $f(g(n))=O(n)$ and $f(n)=Ω(n)$ then $g(n)=O(n).$
21 views

### WKB problem with 4 turning points?

I was recently given a problem that asked to find the solvability conditions for $$\epsilon^2y''=(W(x)-E)y;\quad y\rightarrow0\text{ as }|x|\rightarrow0$$ where $W$ was some piecewise linear, $W"$-...
23 views

### Big Omega and Not Big Omega proofs

I need to proove these three sentences: $g(n) = n + 2n^3-3n^4+4n^5$ $g(n) = \Omega(n^5)$ $g(n) \neq \Theta(5n^6)$ $g(n) = \Omega(nlogn)$ Now, for the Big Omega I have no clue how to do it, for ...
29 views

### Asymptotic Inner and Outer Expansion for a Function

In the question above, I understand that to compute the outer layer you take x = O(1). Thus this means in the asymptotic expansion the first term disappears since it is so small. However, there is ...
173 views