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

learn more… | top users | synonyms (1)

2
votes
2answers
97 views

Properties of Big $\mathcal{O}$

I have seen in a paper that, if $A=\mathcal{O}(p^2)$ and $B=\mathcal{O}(p)$ then, how can we say that, $A^{-1/2}B$ is diverging? The way I thought is, if $A = \mathcal{O}(p^2)$, then $A^{-1/2}$ = ...
2
votes
1answer
86 views

Functional Equation $f(n) = 2 f(n / f(n) )$

I have the following functional equation: $f(n) = 2 \cdot f\left(\frac{n}{f(n)}\right)$ Under the precondition that $ f(n) = \omega(1) $, monotinic and a initial value $ f(1) = \Theta(1) $ one can ...
1
vote
1answer
78 views

Proving $\Omega$ Notation

Prove the following: $$ \frac{n^2}{4} \log ^2 \left(\frac{n}{4}\right) = \Omega \left(\frac{n^2}{2} \log ^2 \left(\frac{n}{2}\right)\right)$$ Whatever I try to do gets me nowhere, I tried ...
3
votes
2answers
159 views

The integral $\int\ln(x-\ln(x))~dx$

The integral $f(y)=\int_0^y\ln(x-\ln(x))~dx$ is on my mind. I'm not sure if this has a closed form? Maybe we need to use the lambert-W function to solve this one? If it cannot be done in closed ...
4
votes
2answers
82 views

Asymptotics of $1-\prod\limits_{i=0}^{k-1}\left(1-\frac{i}{2^k}\right)$

I am interested in the asymptotics of $$1-\prod_{i=0}^{k-1}\left(1-\frac{i}{2^k}\right).$$ As a rough piece of mostly incorrect work this looks a little like $$1-\prod_{i=0}^{k-1}e^{-i/2^k} = ...
1
vote
1answer
42 views

Asymptotics of the smallest integer for which the number of divisors is the $n$-th prime

I am interested in the function $f(n)$ defined on the positive integers where $f(n)$ is the smallest integer for which the number of divisors is the $n$-th prime. Is there a simple asymptotic form ...
1
vote
0answers
125 views

Asymptotic behavior of the Beta function

Let $B(z_1,z_2)$ be the Beta function, $z_1 = x_1 + iy_1$, $z_2 = x_2 + i y_2$. Suppose that $x_1$, $x_2 > 0$. I want to estimate the behavior of $|B(x_1+iy_1,x_2+iy_2)|$ as $|y_1|+|y_2|\to \infty$ ...
0
votes
1answer
107 views

Calculating Lyapunov exponent

The Lyapunov exponent can be used to describe the asymptotic growth rate of the norm of a product of random matrices acting on a specific vector $X$, and is defined as: $$ \lambda = ...
4
votes
1answer
140 views

Recursive sequence with binomial coefficients

I have a sequence $\epsilon_i$ defined recursively for $i\ge 1$ as follows \begin{eqnarray*} \epsilon_1 &=& \frac{1}{p}\\ \epsilon_n &=& \frac{1}{1-(1-p)^n}\left( 1 + \sum_{j=1}^{n-1} ...
3
votes
0answers
46 views

Growth rate of $\exp(log^{a}(x))$ slower then any power of $x$.

So I'm trying to show that for $0<a<1$ and for $\epsilon >0$ that $\exp((\log x)^{a})=\mathcal{O}(x^{\epsilon}).$ So this amounts to showing that ...
4
votes
1answer
136 views

Asymptotics of the classical occupancy problem

Classical Occupancy Problem. There are $n$ distinct labeled balls in an urn. $k$ of them of uniformly selected with replacement. What is the probability that the sample contains at least one ball ...
0
votes
2answers
45 views

limit with exponential

I am trying to solve asymptotic relation between 2 functions: $$f(n)=2^n*n$$ $$g(n)=\frac {3^n}{n^2} $$ I started to solve $$\lim_{x\to \infty} \frac{2^n*n^3}{3^n}=\lim_{x\to \infty} (\frac ...
1
vote
1answer
197 views

Showing (1 - polynomial fraction) raised to a polynomial power is a negligible function

Let $P(k)$ and $Q(k)$ be two polynomials ($k>0$). Let $\mathrm{neg}(k)$ be a negligible function for sufficiently large $k$ (see Appendix on question for definition). Does someone know how to show ...
12
votes
6answers
448 views

Asymptotic behaviour of a multiple integral on the unit hypercube

A few days ago I found an interesting limit on the "problems blackboard" of my University: $$\lim_{n\to +\infty}\int_{(0,1)^n}\frac{\sum_{j=1}^n x_j^2}{\sum_{j=1}^n x_j}d\mu = 1.$$ The correct claim, ...
3
votes
1answer
140 views

Bound of the sum $\sum_{p\le n}\frac{1}{\log(p)}$

While doing a sum I came to the sum $\displaystyle\sum_{p\le n}\dfrac{1}{\log(p)}$. Where the $\log$ is the natural logarithm. It was easy to prove that $\displaystyle\sum_{p\le ...
1
vote
2answers
72 views

Asymptotics of two expressions involving logarithms

(As I am new to algorithmic complexity so), EDIT: please give solutions for large x (means as x->infinity) !
7
votes
0answers
78 views

Partitioning points with a line

Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it? Let $p_{m, n}$ be that number. Apparently ...
1
vote
0answers
68 views

Newton polygon and asymptotic behavior near a singular point

As we know, Newton polygons could be used to determine the Puiseux series of algebraic curves (see, for example, Kirwan's Complex Algebraic Curves, chapter 7). Different branches correspond to ...
4
votes
2answers
465 views

Understanding definition of big-O notation

In a textbook, I came across a definition of big-oh notation, it goes as follows: We say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$|f(x)| \le C|g(x)|$$ whenever $x \gt ...
6
votes
1answer
170 views

How fast does the function $\displaystyle f(x)=\lim_{\epsilon\to0}\int_\epsilon^{\infty} \dfrac{e^{xt}}{t^t} \, dt $ grow?

Let $x$ be a positive real number and $f(x):=\lim_{\epsilon\to0}\int_\epsilon^{\infty} \dfrac{e^{xt}}{t^t} \, dt $. How fast does this function grow ? In other words can we find a good asymptote for ...
1
vote
0answers
42 views

Can I use the Big-O (Landau) notation to “segment” the set of positive increasing real functions?

Let functions $f(n)$ and $g(n)$ be increasing in $n$. I am trying to say the following precisely: As $n\rightarrow\infty$, if $f(n)$ is "smaller" than $g(n)$ then $A$ is true, and if $f(n)$ is ...
2
votes
2answers
228 views

Asymptotics of ${2^n \choose n}$?

How can one compute the asymptotics of ${2^n \choose n}$? I know it is bounded below and above by $\left(\frac{2^{n}}{n}\right)^n$ and $\left(\frac{2^{n}e}{n}\right)^n$. If I plug in Stirling's ...
1
vote
3answers
47 views

I have an answer for an asymptotic analysis, which i cannot accept. please explain me where i go wrong.

We have the following function definitions: \begin{align*}f_1 (n) &= n^{n^{\frac{1}{2}}} \\ f_2 (n) &= 2^n \\ f_3 (n) &= n^{10} 2^{\frac{n}{2}} \\ f_4 (n) &= \sum_{i=1}^{n} (i+1) ...
1
vote
0answers
26 views

Can an entire $f$ satisfy $x>k | f(x+yi)=\ln(x+yi+z)+o(1) $?

Let $z$ be a complex number. Let $i$ be the imaginary unit. Let $x,y,k$ be positive real numbers. Consider $$x>k | f(x+yi)=\ln(x+yi+z)+o(1) $$ true for all $x>k,y$ and some $k,z$. Is there ...
9
votes
2answers
263 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
1
vote
2answers
117 views

What is the order of growth of the parameterized recurrence relation given below?

Given two parameters $a$ and $b$ (both positive integers), please estimate the order of growth of the following function: $$F(t)=\left\{\begin{array}{ll} 1, \, &t\le a \\ F(t-1) + b\cdot ...
2
votes
1answer
48 views

Asymptotics for $p$-series with $p=1/2$

Reading solutions to a practice exam, and I come across this: $$ O\left(\sum_{d \leq \sqrt{x}} {1 \over \sqrt{d}}\right) = O\left(x^{1/4}\right). $$ There are $O(\sqrt{x})$ terms in the sum, which ...
0
votes
3answers
1k views

merge sort vs insertion sort time complexity

How do I solve exercise 1.2-2 from Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen Would I need to set both sides equal to each other and solve for n?
4
votes
1answer
75 views

Asymptotics of $\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$

I have the following formula which appears numerically to be exactly $4n$ asymptotically. $$\sum_{i=1}^n {n \choose i}2^i \frac{i+1}{i^{\frac{n + 1}{2}}}$$ What can one do to prove this?
0
votes
1answer
51 views

a question concerning asymptotics

I have a rather simple question I need an answer to that I have been unable to answer and was wondering if anyone knew any results that pertain to this. It's very simple to state and I believe the ...
7
votes
1answer
177 views

Order and type of an entire function $f$ such that the numbers $f^{(n)}(0)$ are integers.

Let $f$ be an entire function with order $p=1$ and such that the numbers $f^{(n)}(0)$ are integers. Then show that the type $\sigma$ is at least $1$. I appreciate any suggestions.
6
votes
3answers
105 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
2
votes
1answer
56 views

Show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$

Another question about asymptotic approximations. We are asked to show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$ I'm stuck tho and can use help. What I did is: ...
7
votes
1answer
212 views

PDE : Mixture of Wave and Heat equations

Today I was given the following equation : $$\frac{1}{c^2}u_{tt} + \frac{1}{D}u_t = u_{xx}$$ with initial conditions : $u(x,0) = 1$ if $|x|<L$ and $0$ otherwise, $u_t(x,0) = 0$. So fairly simple ...
0
votes
1answer
38 views

Check my short proof - asymptotic approximation, which function is bigger

The goal of this exercise is to show that $\ln(n+1)-\ln(n) = O(\frac{1}{n})$ what I did is: I used the fact that if $f=O(g)$ then $\frac{f}{g}=O(1)$. $\ln(n+1)-\ln(n)=\ln(\frac{n+1}{n}) = \ln(O(1))$ ...
2
votes
1answer
53 views

Problem finding limit - which function is asymptotically larger

I have a homework question, so please don't answer fully but I would appreciate a push in the right direction. Basically we need to figure out if $n^{n+\frac{1}{2}}e^{-n}$ is larger,smaller, or equal ...
1
vote
0answers
46 views

Asymptotics for prime factors

Am I correct in assuming that the same result: $$ N_k(x):=\ \mid\{n\leq x : \Omega(n)=k\}\mid \ \sim \frac{x}{\log x}\frac{(\log_2 x)^{k-1}}{(k-1)!}\ (x \rightarrow \infty) $$ also holds for: $$ ...
4
votes
1answer
34 views

Find asymptotics for solution $x$ of $(x+1)^{\frac{n+1}{n}}-x^{\frac{n+1}{n}}=5$

It is easy to see that for any $n\geq 1$, the equation $(x+1)^{\frac{n+1}{n}}-x^{\frac{n+1}{n}}=5$ has a unique positive solution ; call it $x_n$. Is there a simple asymptotic formula for $x_n$ ? I ...
7
votes
1answer
209 views

Asymptotic formula for almost primes

I have developed a formula for almost primes which is far more accurate asymptotically than Landau's well known $$\pi_k(n) \sim \left( \frac{n}{\log n} \right) \frac{(\log\log n)^{k-1}}{(k - 1)!}$$ ...
1
vote
1answer
72 views

$\pi(x)$ asymptotic as integral $1/\log t$

From the prime number theorem we know that $\pi(x)\sim x/\log x$, i.e. $\dfrac{\pi(x)\log x}{x}\rightarrow 1$ as $x\rightarrow \infty$. How can we use that to show that ...
0
votes
1answer
31 views

Big-O problem, need help

f(n) = max(n^2, n^1.5 log^16 n) f(n) should be O(n^2),Omega(n^2), O(n^1.5 log^16 n), or Omega(n^1.5 log^16 n)? Can anyone help me with it and explain why?
1
vote
2answers
93 views

Is there an “interesting” function that grows faster than $n^{kn}$ but slower than $2^{2^n}$ — relates to understanding googolplex

Motivation: I'm looking for some sort of convenient fact I can use to grasp the size of a googolplex. For a googol we observe a convenient one; it's very nearly equal to 70!. But for a googolplex I ...
3
votes
1answer
57 views

The statements $f(n) = O(n^{\epsilon})$ for all $\epsilon > 0$ and $f(n) = n^{o(1)}$.

Consider the statements \begin{align} \tag{A} f(n) &= O(n^{\epsilon}) \text{ for all } \epsilon > 0 \\ \tag{B} f(n) &= n^{o(1)} \end{align} Questions: It's clear that (B) implies (A). ...
1
vote
1answer
72 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
3
votes
1answer
61 views

Equivalent of a recurrence sequence [duplicate]

Let $x_{0} = 2$ and $x_{n+1} = x_{n} + \ln(x_{n})$, how can I find an asymptotic equivalent of this sequence say, to the third term? (This is not homework, it was a problem in the Oral Examination ...
1
vote
1answer
83 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
3
votes
1answer
96 views

Cesaro means and equivalent sequences

Let $(u_n)$ be a sequence of complex numbers that converges in mean (Cesaro convergence). Let $(v_n)$ be a sequence such that $v_n\sim u_n$. Does the sequence $(v_n)$ converge in mean? Here is ...
2
votes
1answer
55 views

$x^2-\log x = u $ asymptotic behaviour

Find the asymptotic behaviour as $u \to \infty$ of the solutions of $x^2-\log x = u$. Is there a standard method to solve this kind of problems? May the fact that we obviously know the derivative of ...
1
vote
1answer
38 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
0
votes
3answers
63 views

Why $x=\pm1$ is not an asymptote of $\frac{x^3}{x^2+1}$?

By long division, $f\left(x\right)=\frac{x^3}{x^2+1}$is equal to $x-\frac{x}{x^2+1}$. Therefore, there is an asymptote $y=x$. But why there is no an asymptote $x=\pm1$? How to determine whether the ...