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

learn more… | top users | synonyms (1)

1
vote
2answers
306 views

Deciding whether a function is O(n), Ω(n), or Θ(n)

First of all, this is my homework question, i have my answers and i want to be sure whether i am missing something. I have difficulties about deciding whether f(n) is O(g(n)), Ω(g(n)), or Θ(g(n)): ...
1
vote
1answer
543 views

Rate of growth of exponential functions

I have difficulties about proving the following: Prove that exponential functions $a^n$ have different orders of growth for different values of base $a>0$. It looks obvious that when $a=3$ it ...
1
vote
1answer
95 views

Asymptotic behaviour of a sequence

We fix $\alpha >0$, and we look for the asymptotic behaviour when $n \to +\infty$ of $$u_n=1^{\alpha n}+2^{\alpha n}+\cdots+n^{\alpha n}.$$ Any suggestion?
3
votes
1answer
136 views

What happened to the Mertens constant in the strong prime twins conjecture ??

To estimate the amount of primes in an interval $\left(2,x\right)$ one might naively sieve by computing $ x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right)$ ...
1
vote
1answer
148 views

How do we show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$

Basically I'm wondering how I can show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$. Any ideas? Thanks a lot!
1
vote
2answers
65 views

Roots of the equation $I_1(b x) - x I_0(b x) = 0$

I'm interested in the roots of the equation: $I_1(bx) - x I_0(bx) = 0$ Where $I_n(x)$ is the modified Bessel function of the first kind and $b$ is real positive constant. More specifically, I'm ...
1
vote
1answer
45 views

Limits of entire functions

Given an entire function $f \left(x \right)$, which entire function $g \left(x \right)$ is asymptotic to $f \left(x \right)$ as $x \rightarrow \infty$ and asymptotic to $1$ as $x \rightarrow 0$? When ...
2
votes
2answers
152 views

Asymptotic behavior of entire functions

Which entire function $f\left(x\right)$ goes asymptotically to $\dfrac{e^{-x}}{x}$ as $x$ goes to infinity with $x$ positive? That is, $\left(e^{-x}/x \right)/f \left(x \right) \rightarrow 1$.
2
votes
1answer
390 views

Big O notation: relation between Omega and Big O?

Can I do this if I need to proove something for $\Omega$: $f(n) \in \Omega(g(n)) \iff g(n) \in O(f(n))$?
0
votes
1answer
94 views

For $f(n)$ find a simple $g(n)$ such that $f(n)=\Theta(g(n))$

I have to find a specific $g(n)$ such that $f(n)=\Theta(g(n))$. $$f(n) = \sum_{i=1}^n3(4^i)+3(3^i)-i^{19}+20$$ I suppose that this can be solved as integrating this formula, but i don't know how and ...
1
vote
0answers
83 views

Bounding the product of a sequence

I am trying to find an upper bound for the following sequence: $$(1-p_1)(1-(p_1+p_2))\cdots(1-(p_1+\cdots+p_n))$$ with $n$ groups to multiply. I have written it like this: $$\prod_{i=1}^n \left({1 ...
0
votes
1answer
82 views

Asymptotic of a particular integral

This is in relation to my question here. I am reading from this paper and specifically the doubt is from a statement on page 177. Suppose $\alpha\in(0,2)$ and $t_i=ih$ for some fixed $h>0$ and ...
1
vote
1answer
576 views

Meaning of algebraic decay

I am reading the paper here and I am running into a few roadblocks. One of them was resolved here and now I am stuck at another. (Pg 177) Suppose $\alpha\in(0,2)$ and $t_i=ih$ for some fixed $h>0$ ...
0
votes
1answer
769 views

solving recurrence relation by substitution method and find asymptotic bound

Solve the following recurrence relations and give a bound for each of them. $T(n)= 2T(n-3)+1$ $T(n) = 5T(n-4)+n$
0
votes
1answer
1k views

Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$

Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Here's what I've come up with, but I'm not ...
5
votes
1answer
135 views

An estimate of a series

Suppose $s$ is not an integer, let $\lambda(s)=\min_{n≥0}|s+n|$. Show that $\sum\limits_{n=1}^{\infty}(\frac{1}{n+s}-\frac{1}{n})\ll\frac{1}{\lambda(s)}+\log(|s|+2)$.
3
votes
1answer
344 views

Techniques for asymptotic growth comparison between complicated expressions

For the following functions: $$\frac{2^n}{n + n \log n}$$ and $$4^{\sqrt{n}}$$ I'd like to compare their asymptotic growth as $n \to \infty$. Is there any other way to do that other than using ...
0
votes
1answer
69 views

Finding the limit of a summation in order to find Asymptotic Comlexity [duplicate]

I havent done this in a while so I was hoping someone can remind me how to do this, I need to find the limit of this summation: $$\lim_{n \to \infty}{\displaystyle\sum_{k=1}^{n} \frac{1}{k^2}} $$ ...
-1
votes
1answer
185 views

How to find asymptotic entire functions?

I want to know how to find analytic functions $f(z)$ that are asymptotic and analytic on and near the real line of functions of the type $\ln(C +\exp(P(z^2)))$ where $C$ is a complex constant and $P$ ...
2
votes
1answer
377 views

Big o notation $( n \log n + n \log(n^{\log n}))$

I'm trying to transform this: $$n \log n + n \log(n^{\log n})$$ into big O notation. I can't get to reduce the right part of the addition... Neither of these work: $$n^{\log n} ...
0
votes
1answer
3k views

What does it mean when you say that the function is bounded?

What I figured is that it means that the function has an upper bound, however I came across this text: Here since g(x) either equal or less to f(x), |g(x) / f(x)| must be bounded right? Since the ...
3
votes
1answer
114 views

BigO sorting complexity help

Given a bit sequence of length a, what is the minimum number of comparisons needed to determine if it contains a pair of consecutive 1's in BigO notation
2
votes
1answer
371 views

Lower bound for matrix sorting?

Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem. I found that it is $O(n^2logn)$ by just ...
1
vote
1answer
132 views

Difficulty proving / disproving the following equalities relations ( Big Ω)

I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations. Here are the three relations: $ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $ ...
0
votes
2answers
549 views

Asymptotic upper bound in Big-O for $T(n)=T(n-1)+3n-5$. Proof using induction

I need to prove using induction Asymptotic upper bound in Big-O for $$T(n)=T(n-1)+3n-5$$ So I tried expanding $$\begin{align} T(n) &= T(n-1) + 3n - 5 \\ &= T(n-2)+ 2(3n-5) \\ &= T(1) ...
2
votes
1answer
85 views

Prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$

How do I prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$? I have no idea where to start but I tried plotting the graph in Google and noticed that $\log{\log{n}}$ is very close to 0. But ...
4
votes
3answers
851 views

Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $ where $(f+g)(n) = f(n) + g(n) $ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
0
votes
1answer
71 views

if $a= O(N^2)$, can I also say $a=O(N^4)$?

if $a=O(N^2) $ then according to the big oh definition I didn't see why we can't say $a= O(N^4)$ or $= O(N^8)$
0
votes
1answer
194 views

Asymptotic Notation more specifically, Big-O notation

How the functions in the class $O(d)^d$ and $\epsilon^{1/O(d.4^d)}$ looks like..? where $\epsilon$<1. I am really confused with this complicated Big-O notations Can you please help me out.
6
votes
3answers
164 views

Is there a minimal diverging series?

Is there a function $f:\mathbb{N} \to \mathbb{R}^+$ s.t. its series $\Sigma_{i=0}^\infty f(n)$ diverges but the series for all function in $o(f)$ converge?
1
vote
0answers
31 views

Evaluating a simple sum bound

I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution. I would like to advise with you if this is the right way because It is really getting more complicated than It ...
2
votes
1answer
95 views

Asymptotic behavior of $\cos(\sqrt{4n+1}x)-\cos(\sqrt{4n+\alpha}x)$

While reading a paper in physics i came across asymptotic behavior of $\cos(\sqrt{4n+1}x)-\cos(\sqrt{4n+\alpha}x)$ and it was written this is equal to $O(n^{-1/4})$ for any real $\alpha$. I tried to ...
1
vote
1answer
45 views

Simplifying Equation - Asymptotic analysis

The textbook I'm using for the course Introduction to Algorithms class has the following statement in it: The equation of such a line is $\log (T(N)) = 3 \log N + \log a$ (where a is a ...
4
votes
6answers
298 views

Asymptotic expansion of $ I_n = \int_0^{\pi/4} \tan(x)^n \mathrm dx $

I'm trying to compute the asymptotic expansion of $$ I_n = \int_0^{\pi/4} \tan(x)^n \mathrm dx $$ Here is what I've done: Change of variable $$ t= \tan x $$ $$ I_n = \int_0^1 \frac{t^n \mathrm ...
0
votes
1answer
82 views

If not an upper bound, is it a lower bound?

I wanted some help with a bounding question. The question asks that if $f$ is not an upper bound on $g$, is it a lower bound? $f,g: \mathbb{N} \to \mathbb{N} \cup \{\infty\}$. By definition for an ...
0
votes
1answer
184 views

Proof for asymptotic tight bound when $C=a_k/2$

In an algorithms lecture in school theres a proof for asymptotic tight bound like: Take $C=a_k/2$ and show that $f(n) \ge \frac{a_k}{2} n^k$ when $n > N$ for some $N$. $$\begin{align} ...
2
votes
1answer
128 views

How to find asymptotic behaviour?

How do we find asymptotic behavior of Hermite polynomials? I tried to check, but i can only find the final expression but not the method.
1
vote
2answers
109 views

Does little-o notation imply going into infinity?

Let $f(n)=o(g(n))$. By definition there exists $n_0$ so that for all $n>n_0$ it holds that $\varepsilon \cdot g(n) \geq f(n)$ for $\varepsilon>0$ however small. So, in plain language, starting ...
0
votes
1answer
58 views

for positive functions $f(n)$ and $g(n)$, can $f(n)$ be in $\mathcal{O}(g(n))$ and $\Omega(g(n))$?

For positive functions, is it possible for $f(n)$ to be lower bounded by $g(n)$ if its already being upperbounded by $g(n)$? If $f(n) = g(n) = n$, then doesn't that mean $g(n)$ is a lower and ...
2
votes
1answer
80 views

Asymptotic expansion of $ u_n = \int_0^1 \ln(1+t^n) \mathrm dt $

I would like to know how I can compute the asymptotic expansion of: $$ u_n = \int_0^1 \ln(1+t^n) \mathrm dt $$ Using the dominated convergence theorem, we get: $$ u_n \sim \frac{\pi^2}{12n}$$ How ...
0
votes
5answers
123 views

How to prove that $\log_2(n!) = \Theta(n\log_2[n])$?

My first thought was to use $$\lim_{n\rightarrow\infty}\frac{n!}{n^n} = 0$$so I thought it should be $$\log_2n!=O(n\log_2n=\log_2n^n)$$ but I was told that $$\log_2n!=\Omega(n\log_2n)$$ is also true. ...
0
votes
1answer
61 views

asymptotic expansion, interpretation

I am interested in asymptotic behavior of a function at infinity: $$ f(r)=\frac{0.04962 e^{-2 r} (r-1.000)}{\left(\left(e^{-2 r}\right)^{2/3}+0.06119\right)^2 r} $$ Tried ...
1
vote
1answer
116 views

Is the sum always bigger than $n^2$?

Let $s(n)$ an arithmetical function defined as $$s(n)=(p_1+1)^{e_1} (p_2+1)^{e_2} \cdots (p_m+1)^{e_m}$$ where prime factorization of $n$ is $n=p_1^ {e_1} p_2 ^{e_2} \cdots p_m^{e_m}$. (For example, ...
1
vote
1answer
92 views

$x \sim y \implies \pi(x) \sim \pi(y) $ and repeated applications of PNT

Let $\sim$ mean if $a \sim b$ then $\lim_{x \to \infty} \frac{a}{b} =1.$ The following is a threshold question. It seems that $x \sim y \implies \pi(x) \sim \pi(y).$ Pf. $\pi(x) \sim \frac{x}{\log ...
2
votes
1answer
48 views

A number-theoretical estimation-inequality

I have some trouble understanding the following number-theoretical estimation: $$\sum_{k\le \sqrt{n}} (1-k^2/n)^{1+o_n(1)}=n^{1/2+o(1)} \ (n\to\infty),$$ where $o_n(1)$ denotes a $o(1)$ function ...
1
vote
1answer
89 views

Help finding Complexity in Big-O notation

I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
3
votes
1answer
144 views

Laplace method help

$$\int_{0}^{\infty} \frac{e^{-x \cosh t}}{\sqrt{(\sinh t)}}dt$$ I'm trying to use Laplace's method to find the leading asymptotic behavior as $x$ goes to positive infinity, but I'm having some ...
1
vote
1answer
357 views

Prove $n^\frac{1+2}{\sqrt{\log n}} = O(n \log n)$

Prove that $$n^\frac{1+2}{\sqrt{\log n}} = O(n\ \log n).$$ I want to compute the two growth rates by using L'Hôpital's rule: $$\lim_{n\to \infty} \frac{f(n)}{g(n)}$$ so I get something like ...
0
votes
1answer
898 views

Dominant term and Big Omega

For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation. $$n^3+n^2\log_2(n)+n^3\log_2(n)$$ So, I ...
0
votes
3answers
129 views

Example of a function according to Big-Oh rules

I am having difficulty understanding the Big-Oh rules. For example , here is a question : Find example of functions ( which are not negative ) $d(n),f(n),e(n),g(n)$ such that $d(n)$ is $O(f(n))$ and ...