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

learn more… | top users | synonyms (1)

6
votes
1answer
113 views

Asymptotics of $\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}$, is it $\frac{2}{\pi n}$?

I am trying to work out the asymptotics of $$\frac{\sum _{i=0}^{\lfloor n/2 \rfloor} {2(n-2i) \choose n-2i} {n \choose 2i} {4i \choose 2i}}{2^{3n - 1}}.$$ My numerical experiments suggest it might ...
1
vote
1answer
39 views

What is the limit of the below functions when n tends to inifinity?

What is the value for the functions in the image when limit n tends to infinity?. Also what is the asymptotic complexity (big $O$ notation) for all the four functions?. $$\begin{aligned}f_1(n) &= ...
0
votes
1answer
14 views

Big-Oh of $(\log_bn)^c$ is $O(n^d)$

I'm a CS freshman. In my discrete math textbook, it says ... whenever b > 1 and c and d are positive, we have $(\log_bn)^c$ is $O(n^d)$, but $n^d$ is not $O((\log_bn)^c)$ But why? Using ...
0
votes
2answers
41 views

Why does this inequality stand?

I stand that $\log n=O(n^{\epsilon})$ for any $\epsilon >0$. At a previous example we have shown that $$e^{n^{\epsilon}} \geq \frac{n^{\epsilon d}}{d!}$$ where $d=\lfloor ...
2
votes
1answer
44 views

Show that $f(x) = O(1/x)$

Let $f:\mathbb{R}\to\mathbb{R}$ such that $f\ge 0$, monotonically decreasing and $\int_0^\infty f(x) \ dx < \infty$. Prove that $f(x) = O(1/x)$. So basically, both $f(x)$ and $1/x$ are ...
4
votes
1answer
66 views

How to use Laplace method to get the asymptotic expansion of multiple integral

I meet difficulty when I try to get the asymptotic behaviour of multiple integral as x tends to plus infinity. And $-1<$p$<1$ $$\int_x^{+\infty}\int_x^{+\infty}e^{-{\frac{1}{2\sigma^2(1-p^2)}\ \ ...
1
vote
2answers
66 views

Divide and Conquer in big O notation

I've got a problem – divide-and-conquer part of my program divided my problem into 2 parts: 1/7 and 5/7 of a problem + merging in a linear time. I need to know it's asymptotic complexity. I know, it ...
6
votes
0answers
43 views

Comparing asymptotic forms of series

I've run into some asymptotic analysis in research here and there and largely it feels pretty magical to me. My research has led me to consider the following question which I haven't the slightest ...
1
vote
0answers
35 views

Hamming weight in multiple label

Assume you have a $N$ balls. You give each ball $T$ different labels randomly from $\{0,\dots, N-1\}$. So hamming weight of each of labelling varies from $0$ to $\lceil\log_2 N\rceil$. What is ...
5
votes
2answers
112 views

How to get the asymptotic form of this oscilatting integral?

So the integral is like this: $$\int_1^\infty \frac{\cos xt}{(x^2-1)\left[\left(\ln\left|\frac{1-x}{1+x}\right|\right)^2+\pi^2\right]}\mathrm{d}x$$ The question is how to get the asymptotic form of ...
0
votes
0answers
12 views

Finding the correct asymptotic functions

in an exercise of algorithms, I have to find a function $f(n)$ that is $Ω(n^2)$ and such that for every $n>0$ is $f(n)<n^2$. I also need to find a function $g(n)$ which is $Ω(n^2)$ but not ...
0
votes
1answer
40 views

What is the asymptotic behavior of the function counting the number of (not necessarily distinct) prime divisors?

From http://en.wikipedia.org/wiki/Arithmetic_function#.CE.A9.28n.29.2C_.CF.89.28n.29.2C_.CE.BDp.28n.29_.E2.80.93_prime_power_decomposition Ω(n), ω(n), νp(n) – prime power decomposition The ...
2
votes
1answer
22 views

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$.

True or false. If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f-g)(n) =\Theta(n^4)$ where we define $(f-g)(n)=f(n)-g(n) \forall n$. I believe this is false. Take $f(n) = 4n^2, g(n) = ...
3
votes
1answer
26 views

Find the asymptotic behavior of solutions of the equation

Find the asymptotic behavior of solutions $y$ of the equation $$x^5 + x^2y^2=y^6,$$ which tends to $0$ when $x$ tends to $0$. My solution: if $y=Ax^n$, then $$x^5 + A^2x^{2+2n}=A^6x^{6n}.$$ If ...
0
votes
2answers
47 views

How to prove order of equation using Big-Oh notation? [closed]

How can I prove this order equation using Big-Oh notation? $$O(3n^3+2n^2+5) = n^3$$
-1
votes
2answers
42 views

How to solve recurrence equation with logarithms using the Master Theorem

how do you solve this equation of recurrence? $T(1) = 1$ $T(n) = 2T(\frac{n}{3})+n*log_2(n)+1$ The problem is the term $n*log_2(n)$. Can I only consider only $n$ as it's the larger then $log_(n)$ ...
2
votes
1answer
36 views

Finer asymptotic estimate of an integral

I'm studying the asymptotic behaviour for large $n\in \mathbb N$ of $\displaystyle \int_1^\infty \frac{1}{1+t^{n+1}}$ Using the substitution $u=(n+1)\ln(t)$, $$\displaystyle \int_1^\infty ...
9
votes
1answer
99 views

An upper bound for Summative Fission numbers

I recently found OEIS entry A256504 and have been playing around with this sequence a bit. Its definition is: For a positive integer $n$, find the greatest number of consecutive positive integers ...
1
vote
1answer
24 views

Asymptotic Distribution of Quantiles

In order to prove that the sample $p$-percentile $x_p, p \in [0,1]$ from a sample of $n$ is asymptotically normally distributed as $n\to\infty$, it is necessary to show the following two limits. They ...
0
votes
1answer
49 views

Prove that $2^{n+1} = \Theta(2^n)$?

I need to prove that $2^{n+1} = \Theta(2^n)$? To do this, I need to show that there are positive constants $c_1,c_2$ such that $$c_1 2^n \le 2^{n + 1} \le c_2 2^n$$ ...for all sufficiently large ...
0
votes
1answer
43 views

Disprove $f(n) = 2^{2n}$ is $O(2^n)$

Disprove $f(n) = 2^{2n}$ is $O(2^n)$ Informally I know that this means we have to show that $2^{2n}$ grows much faster than $2^n$. More formally, I know that we need to show that for any $N$, ...
0
votes
3answers
58 views

Prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$

I need to prove or disprove $f(n)$=$2^{n+1}$ is $O(2^n)$. I believe this statement is true, so I want to prove it. I know that $f(n)$ is $O(g(n))$ if there are positive constants $C$ and $k$ such ...
0
votes
0answers
27 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
0
votes
1answer
47 views

Asymptotic sums and liminf

Given an arithmetic function $f(n)>0$ with $$\liminf \frac{g(n)}{f(n)}=C$$ for a certain constant $C$ and another function $g(n)>0$, in the study of the asymptotic bound for $$ \sum_{n\leq x} ...
0
votes
0answers
57 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
2
votes
1answer
32 views

Big O notation proof for a divided problem

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear ...
1
vote
2answers
51 views

How can I show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$

I am preparing for an exam, and one of the problems on the study guide is: Show that $\sum \limits_{i=1}^n i^2$ is $O (n^3)$ If we declare n as some arbitrary number 5, then our summation would ...
4
votes
1answer
104 views

Is $\sum_{k\leqslant n} f'(k)f'(n-k) \asymp f'(n)f(n)$ when $f'$ is positive decreasing?

In this answer of a question of mine, the user Homegrown Tomato gave a nice argument that somewhat shows that $$\int_{\substack{t+s\leqslant x \\ t,s \geqslant 0}} f'(t)f'(s)dtds \asymp ...
1
vote
1answer
19 views

Order estimates

QUESTION: Suppose $y(x) = 3 + O (2x)$ and $g(x) = \cos(x) + O (x^3)$ for $x << 1$. Then, for $x << 1:$ (a) $y(x)g(x) = 3 + O (x^2)$ (b)$ y(x)g(x) = 3 + O (x^4)$ (c) $y(x)g(x) = 3 + O ...
2
votes
1answer
37 views

what is wrong with this proof? (proving the transitive property of Big O)

So the problem is if $f(n) \in O(g(n))$,and $g(n) \in O(h(n))$ then $f(n) \in O(h(n))$ Assume $f(n) \geq 0, g(n) \geq 0, h(n) \geq 0$ Proof: From assumptions, ...
1
vote
1answer
287 views

Limit involving tetration

Let the notation be $a^{\wedge\wedge}b = \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_{b\,times}$ for tetration. My mentor conjectured the following: Let $n$ be a positive integer, then let $A(n)$ be ...
3
votes
1answer
41 views

Big O Notation and negative “n”

So I'm studying big $O$ notation right now and am working through a problem and got $O(x^{-10})$ and I'm just wondering if it's possible to even have a term with $O(x^{-n})$ because I've never come ...
2
votes
2answers
44 views

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$

Use Laplace's method with $\int_{0}^{\infty} e^{x(3u-u^3)}du$ as $x\rightarrow \infty$. I'm confused about how to taylor expand about u=1? How do I continue? Obviously first of all I have converted it ...
1
vote
2answers
27 views

does $f(n) \neq O(g(n))$ implies $g(n)=O(f(n))$ [duplicate]

Im pretty sure it doesn't, but how can I be sure? Was thinking by using $$f(x) = \sin(x) + 2$$ and $$g(x) = \cos(x) + 2$$ Thanks!`
0
votes
1answer
26 views

Big Theta of this modification of the secondary branch of the Lambert W function

I am looking to find the big-$\Theta$ of $-W_{-1}(-\frac{a}{n})$ in terms of elementary functions where $a$ is a constant. Looking around and I find that this should be $O(\log(n))$ and with maxima I ...
3
votes
1answer
47 views

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$

Show that $\int_{0}^{\infty} e^{ix(\frac{t^3}{3}+t)}dt \sim \frac{i}{x}$ I thought that you would use the method of stationary phase, but the maximum of $\frac{t^3}{3}+t$ occurs at $+/- i$. So how do ...
1
vote
0answers
44 views

Question about your function,

I'm Xavier Vigan, a physical oceanographer. I've been using your $f(x)=\dfrac 12 \times \left(X+C-\sqrt{S+(X-C)^2}\right)$ function to calibrate quantile vs quantile plots. Because of the shape of ...
0
votes
0answers
31 views

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$

Finding the asymptotic expansion of $\sin(3x)$ using asymptotic sequence $\{\ln(1+x^n)\}_n$. In the notes and lectures the only example that was given was an expansion for $\tan(x)$ where she ...
2
votes
1answer
30 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
4answers
55 views

Big-O notation — is it mainly used to classify rate of growth or rate of decay to zero?

For example, $e^{x} = 1 + x + x^2/2 + O(x^3)$, and we interpret $O(x^3)$ as the remainder term that goes to zero like $x^3$. What's the primary usage of Big-O notation? (strictly in math classes, ...
0
votes
3answers
26 views

relationship between Big $O$ notation and limit

If I have a function $f(n)$ such that $f(n) \geq 0$ for all positive integers $n$ and that $\lim\limits_{n\to \infty} f(n) = 0$, then can I conclude that $f(n) = O\left( \dfrac{1}{n^k}\right)$ for ...
3
votes
1answer
54 views

length of the curve $y=x^n$ in the unit square

Let $l_n$ be the length of the curve $y=x^n$ in $[0,1]\times[0,1]$. Then obviously $\lim_{n\to\infty}l_n = 2$. What about $\lim_{n\to\infty}(n(2-l_n))$ ? The formula $l_n = ...
0
votes
1answer
39 views

can use diagonal matrix in a formula to figure out how many characters would occur in all substrings of a string 's'?

Math experts - I'm working through a simple "big O" analysis of algorithms problem comparing two approaches to the longest substring problem. One approach is brute force: checking all possible ...
0
votes
1answer
24 views

Little o notation within another little o

To prove $e^{x + o (x)} = 1 + x$ as $x \rightarrow 0$, I can do it directly: $\lim_{x \rightarrow 0} \frac{\log (1 + x) - x}{x} \overset{\text{l'hopital}}{=}\lim_{x \rightarrow 0} \frac{(1 + x)^{- ...
3
votes
1answer
47 views

Density of linear combination

Let $r_1, \ldots, r_n$ be a set of positive reals. Define \begin{equation*} S = \{a_1r_1+\cdots+a_nr_n : a_i\in \mathbb{N}\}. \end{equation*} Define $\pi(x)= |\{a\in S:a<x\}|$. Is there an ...
2
votes
0answers
35 views

WKB leading order

I'm learning about the WKB method, and I'm applying it to an assignment. The assignment question asks to find the "leading order" WKB expansion for the particular equation. For WKB you make the ...
0
votes
0answers
29 views

how to solve T(n)=T(Logn)+O(1)

Given That $T(1)=1$ Solve following recurrence function $T(n)=T(\log n)+O(1)$ I know the answer is $\log^* n$ but don't know how to prove it. What I tried: $\log(n)+\log(n-1)+\log(n-2)+...+1 = ...
1
vote
2answers
67 views

Does $O(\log^2(x))$ imply $O(x)$

Does $O(\log^2(x))$ imply $O(x)$ I have to prove the following: $$\sum\limits_{\substack{n\in\mathbb N\\n\le x}}\Lambda(n)\log(n)=\psi(x)\log(x)+O(x)$$ Applying partial sum I get; ...
0
votes
0answers
11 views

Deriving information about asymptotics from finitness of a limit

Let $f_1,f_2:\mathbb{R}\setminus\{0\}\to \mathbb{R^+}$ be two $C^1$ functions and $\alpha:\mathbb{R}\setminus \{0\}\to \mathbb{R}$ be a function from a Zygmund class (in particular it is Holder for ...
1
vote
0answers
18 views

How to solve asymptotic recurrence without using Master Theorem

I am working on the following problem. Consider the function $B:\mathbb{N}\to\mathbb{R}$ defined by: $$B(n) = \begin{cases} 1 & \text{if $n\leq 2$,}\\ 3\cdot B(\lceil n/\log_2 n\rceil) + n & ...