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

learn more… | top users | synonyms (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
141 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
46 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
204 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
450 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
145 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
483 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
171 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
233 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
266 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
49 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
179 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
217 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
42 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
55 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
47 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
35 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
211 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
94 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
85 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
39 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 ...
16
votes
4answers
644 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
1
vote
0answers
30 views

Find the order of the following expression as x->0

Could someone help me find the order of the following expression without using the quotient rule? $\frac{1-\cos(x)}{1+\cos(x)}$ I expanded the denominator and the numerator but not sure how I get to ...
3
votes
2answers
181 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
1
vote
0answers
42 views

Asymptotically evaluating integrals with oscillatory behaviour in both numerator and denominator

I have come across an integral that I would like to asymptotically evaluate (to leading order at least) which I have seen no mention of in standard textbooks. I want to evaluate an integral of the ...
1
vote
1answer
110 views

big O notation - explain the equality

$$\sum\limits_{i = 1}^{\log n} {\sqrt {{2^i}} } = O(n) $$ OK, So I understand the equality, but I don't know how to prove it. For my understanding, I need to show that the left side is $\le$ the ...
1
vote
0answers
69 views

How to prove that there are $O(T\ln T)$ zeros in the critical strip of the Riemann zeta function?

Define $F(T)$ as the number of solutions to $\zeta(a+ ti) =0$ for $0\le t\le T$ and $0<a<1$. How to show that $F(T)= O(T\ln T)$? For clarity, $\zeta$ is the Riemann zeta function, $i$ is the ...
6
votes
1answer
254 views

Asymptotic expansion for harmonic sum in two variables

I am interested in determining an asymptotic formula for the double summation of $1/(ab)$, where $a$ is an odd integer ranging between 1 and $k/\sqrt{j}$, $b$ is an odd integer ranging between $a$ and ...
0
votes
1answer
50 views

Big - Oh proof $n^{2^n} = O(2^{2^n})$

But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
4
votes
3answers
264 views

Asymptotic expansion of $J(t) = \int^{\infty}_{0}{\exp(-t(x + 4/(x+1)))}\, dx$

I want to derive an asymptotic expansion for the following Bessel function. I think I need to rewrite it in another form, from which I can integrate it by parts. I am interested in obtaining the ...