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

learn more… | top users | synonyms (1)

0
votes
2answers
24 views

Big $O$ estimate of $(n\log n+1)^2+ (\log n +1)(n^2+1)$

Give the Big $O$ estimate of $(n \log n +1)^2 + (\log n +1)(n^2+1)$ Taking big $O$ of the first function (ignoring constant and exponent), ($n\log n + 1)^2$ we get $O (n \log n)$ Taking big $O$ of ...
0
votes
0answers
21 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
0
votes
1answer
39 views

How to solve a recurrence relation such as $T(n) = 2T(\frac{n}{2}) +$ $\frac{n}{\log (n)}$?

Wikipedia says that the equation cannot be solved using Master's Method. The equation matches with Master's Theorem except for $\frac {n}{\log(n)}$. A youTube tutor (seek time 11:42) solves this ...
2
votes
2answers
31 views

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$.

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$. Since $2^n$ < $2^{n+1}$, you can say $2^{n+1}$ is not $O(2^{n})$ Since $2^n$ is < $2^{2n}$, you can say $2^{2n}$ ...
0
votes
1answer
23 views

Verify answers to these big o notation questions

May someone look over if I did these big o notation problems correctly? Some of them were tricky. 1) $f(x) = 10 = O(10)$ 2) $f(x) = 3x + 7 = O(x) $ 3) $f(x) = x^2 + x + 1 = O(x^2) $ 4) ...
2
votes
3answers
100 views

How does $\log(x^2 + 1)$ become $\log(2x^2)$?

My textbook attempts to take the big O of $\log(x^2 +1)$. It proceeds by saying $x^2 + 1 \le 2x^2$ when $x \ge 1$. But I don't know how it came up with this idea. Question: Why set $x^2+1$ to a ...
0
votes
1answer
21 views

Big-$\mathcal{O}$ notation for CRT and Extended Euclidean Algorithm

I am very unfamiliar with Big-$\mathcal{O}$ run time calculation. I know that for addition the run time is $\mathcal{O}(\log n)$ and for multiplication the run time is $\mathcal{O}(\log^2 n)$. How ...
3
votes
1answer
46 views

Asymptotic elementary expression for the antiderivative of $x^x$

It is well known that there exists no elementary function $f$ with $$\int x^x\,dx \quad = \quad f$$ Is there an elementary function $g$ such that $$\int x^x\,dx \quad \tilde{} \quad g$$ in the ...
0
votes
1answer
45 views

Big oh notation

I am learning big-oh notation and i am wondering if something like $O(\sqrt{x})=O(O(\sqrt{x}))$ is true, and, more importantly, how you can prove this rigorously using the definition of big-oh? ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
28 views

Explain why $f = O(g)$

I am working on a review for a test and I'm trying to figure out how to explain the following problem: Determine if the following statement is True or False. Briefly explain why: If $\,f(n) = ...
1
vote
2answers
41 views

For what sequences $a_n$ does the sequence $(1+\alpha a_n)^n$ converge?

We know $ (1+\alpha/n)^n \rightarrow e^{\alpha} $ when $n\rightarrow +\infty$. Suppose we are given a modified version of the problem: $$ \quad (1+\alpha\cdot a_n)^n \tag{1} $$ The question ...
1
vote
1answer
34 views

Define function F which is big O but not big theta

Searching for one definition of $f : \mathbb{N} \rightarrow \mathbb{N}$ with $f' : \mathbb{N} \rightarrow \mathbb{N} $ defined with $f'(n) := f(n+1) - f(n)$ with the bounderies $f=O(f')$ and $f ...
0
votes
0answers
16 views

Using the WKB approximation to find the values of different positive Eigenvalues $E_n$

Consider $$y''(x)+EQ(x)y=0, Q(x)>0 \mbox{ subject to } y(0)=y(\pi)=0$$ The WKB approximation is (which i've proved) is: $$y(x) = CQ^{-0.25}(x)\sin{(\sqrt{E}\int_0^x\sqrt{Q(t)}dt)}$$ Then the ...
0
votes
0answers
12 views

Singularities of complex exponential and asymptotic expansion

Consider the equation $$L[u(x,t)] = \tilde u(s,t) = \frac{e^{-t\sqrt{s^2-1}}}{s-2}$$ I want to find $u(x,t)$ in the form of an integral. I first need to find the poles and singularities of the ...
1
vote
1answer
42 views

Growth of binomial coefficient

I am interested in the growth of the binomial coefficient ${n\choose n^a}$ for some fixed $a\in (1/2,1]$. Of course, for $a=1$ the binomial constantly equal to $1$. For $a<1$, computations suggest ...
2
votes
0answers
40 views

Asymptotic expansion of integral (Laguerre)

Consider $$L_n = \frac{1}{2\pi i } \oint_{C'} \frac{1}{(1-t)^{\alpha+1} t^{n+1}} e^{-\frac{xt}{1-t}} dt\,\,\,\,(1)$$ where $C'$ is an anticlockwise contour around zero. Now set $\alpha = n$ and I want ...
0
votes
2answers
25 views

Can a function exist that is both $o(g(n))$ and $\omega(g(n))$?

Can a function exist which is both $o(g(n))$ and $\omega(g(n))$? Wouldn't this imply $$m |g(n)| \le |f(n)| \le k |g(n)| $$ If $f(n) = g(n)$ then wouldn't an arbitrary integer $m$ be greater ...
4
votes
1answer
69 views

Estimating $\int_0^x f(x-t)f'(t)dt$

I'm attempting to estimate $\int_0^x f(x-t)f'(t)dt$ in terms of a simple asymptotic expression with an error term for some 'well-behaved' functions, namely $f = O(x)$, of class $C^1$ or higher, with ...
1
vote
1answer
22 views

Asymptotics of a sum of scaled multinomial coefficients

I'm interested in finding the asymptotics of the following (for $p \in [0,1]$) $$\sum_{k=1}^{\lfloor (n-1)/2 \rfloor} \frac{k {n-1 \choose 2k} {2k \choose k}} {4^{k}p^{k}}.$$ The central binomial ...
0
votes
0answers
35 views

Algorithm to efficiently compute$ A^k$

If a symmetric matrix $A$ has SVD $A=U\Sigma U^{\top}$, then $A^k=U\Sigma^kU^{\top}$. What would be the most efficient algorithm to compute $A^k$ such that the worst case time complexity is as low as ...
6
votes
1answer
604 views

Given two real sequences that go to infinity, is it possible to select two subsequences that grow at the same rate asympotically?

Given two positive real sequences $a_n$ and $b_n$ that both diverge to infinity, is it possible to choose two subsequences $a_{s_n}$ and $b_{t_n}$ such that $a_{s_n}/b_{t_n}\rightarrow1$?
3
votes
2answers
69 views

asymptotics of sum

I wanna find asymptotic of sum below $$\sum\limits_{k=1}^{[\sqrt{n}]}\frac{1}{k}(1 - \frac{1}{n})^k$$ assume I know asymptotic of this sum (I can be wrong): $$\sum\limits_{k=1}^{n}\frac{1}{k}(1 - ...
2
votes
0answers
24 views

Asymptotic for degree [duplicate]

How can I find asymptotic for $\chi(n)$, if $\chi^{\chi^\chi} = n$. Is here self-qualification estimation? I tried to take the logarithm of both sides, but to nothing has come.
4
votes
1answer
96 views

asymptotic of $x^{x^x} = n$

How find the asymptotic behavior for $x(n)$ if $x^{x^x} = n$? I supposed that $x = O(\log\log{n})$ and took logarithm two times. So I get $x = O(\frac{\log\log{n}}{\log\log\log{n}})$ Is it right? ...
1
vote
1answer
57 views

Closed-form expression for a sum of reciprocals of factorials [closed]

Is there a closed-form expression for the finite sum $$\sum_{s=1}^{2^{n-1}}\frac1{(s-1)!}$$ as a function of $n$?
0
votes
0answers
27 views

Additive and Multiplicative Error in $n!$ Approximation

Let $S(n)=\sqrt{2\pi n}\big(\frac{n}{e}\big)^n$ be the approximation of interest to $n!$. What are good lower and upper bounds on the following two functions $$(1)\mbox{ }|S(n)-n!|?$$ $$(2)\mbox{ ...
2
votes
1answer
76 views

When is a particular sum $\Theta(n)$?

Define $$S_n = \prod_{x=1}^{\lceil\frac{n}{\ln{n} }\rceil} \left(\frac{1}{\sqrt{n}} + \frac{2x}{n}\left(z_n-\frac{1}{\sqrt{n}} \right)\right) .$$ I am trying to work out necessary and sufficient ...
0
votes
0answers
18 views

Laplace's method with nontrivial parameter dependency

I need to approximate the following integral using Laplace's method: $$ \int_0^{\infty} \frac{x^{\lambda} \lambda^{-x}}{(1+x^2)^\lambda} \\ = \int_0^{\infty} \exp\left(\lambda \log(x) - ...
0
votes
1answer
34 views

algorithmic complexity in Big O notation

Here is the function that is meant to be analyzed f1(n) 1 v ← 0 2 for i ← 1 to n 3 do for j ← n + 1 to 2n 4 do v ← v + 1 5 return v I was wondering if my ...
0
votes
2answers
50 views

Pitfalls/subtleties of $O$ notation

What are some examples of $O$ subtleties? I'm not only thinking of the asymmetry of the $O$ relation, but of the ways in which $O$ constants can depend on nearby parameters, and the fact that the ...
3
votes
1answer
57 views

Given a set of powers of two, how “close” can we come to a prime?

Given a natural $n \ge 2$, we can construct a set of all powers of two from $2^n$ to $2^{4n}$: $$\{2^n, 2^{n+1}, 2^{n+2}, \dots, 2^{4n}\}$$ How close does one of these numbers come to a prime in the ...
7
votes
0answers
85 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
3
votes
2answers
129 views

Asymptotic development of a recurrent sequence

Let $u_0 = 1$ and $u_{n+1} = \frac{u_n}{1+u_n^2}$ for all $n \in \mathbb{N}$. I can show that $u_n \sim \frac{1}{\sqrt{2n}}$, but I would like one more term in the asymptotic development, something ...
0
votes
1answer
26 views

BigOh Complexity: $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$?

Show $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$ Can I do it like this? Since exponent rules/laws allow this: $\frac{x^{3} + 2x}{2x + 1}$ $=$ $\frac{1}{2}x^{2} + 2x$ Must show a constant c>0 and k ...
0
votes
0answers
24 views

When can you replace by an equivalent in a sum or inside some given function?

This question is a follow-up to this question. I was originally going to post it as a comment to robjohn, but decided it should grow into a question of its own. Write $a_n\sim b_n$ if $\lim ...
2
votes
1answer
66 views

Improvements of Dusart's lower bound for $ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}$.

Let $\gamma$ be the Euler-Mascheroni constant. In this paper (Theorem 6.12) it is proved that for $x\ge 2793$, $$ e^\gamma \log x \prod_{p\le x} \frac{p-1}{p}> 1-\frac{1}{5 \left(\log ...
1
vote
0answers
8 views

Strategies for approximating fourier transform of $k$-th power of the $n$-th derivative of a function

For a function $f(x)$ with Fourier transform $\hat{F}(q)$, I'm interested in understanding the relationship of the Fourier transform of a power of a derivative of $f$ to $\hat{F}(q)$. Explicitly, I ...
0
votes
0answers
1 views

Asymptotic distribution of ratio / multiplication of two variables

Suppose $\rightarrow_D $ denotes convergence in distribution. If we know $$ f_1 \rightarrow_D W_1 $$ $$ f_2 \rightarrow_D W_2 $$ Can we say something about the convergence of $$ f_1 f_2 ...
0
votes
0answers
26 views

Orders of growth of typical sequences

It's been a while since I had to deal with some sort of asymptotic analysis so I am a bit rusty and trying to get the basics back together. Since I don't really know where to look for these things, I ...
1
vote
0answers
32 views

Approximate solutions for quintic equation

The other day I asked a question in here about deriving the equations $$u^2\left(\left(1-s_1\right)+3u+3u^2+u^3\right) =\alpha\left(s_0+2s_0u+\left(1+s_0-s_1\right)u^2+2u^3+u^4\right),$$ where ...
1
vote
1answer
26 views

Proving Lower Bound on Catalan Numbers

I'm a student of computer science and was reading through my algorithms textbook about matrix chain multiplication. It brought up Catalan numbers and I was hoping to prove the lower bounds on it. This ...
3
votes
2answers
50 views

Sum of 'inverse' Normal (1/X) random variables. Equivalent resistance calculation

Consider the case of $N$ resistances $R$ connected in parallel. The equivalent resistance of such a circuit is calculated as follows $$ \frac{1}{R_{eq}} = \underbrace{\frac{1}{R} + \frac{1}{R} + ...
1
vote
0answers
25 views

Mutual Asymptotic analysis of the given fucntions

$ f(n)$ = $ 3n^{\sqrt{n}} $ $g(n)$ = $2^{\sqrt{n}log_2n}$ $h(n)=n! $ For all the $3$ pairs of the functions, which one is $Big-O$ of which ? I am unable to compare these functions. Edit : I ...
0
votes
0answers
55 views

How prove this Laplace domain asymptotic behavior $\widetilde{f(s)}\approx 1-(s\tau)^{\alpha}$

I have know Long-tailed waiting time pdf with the asymptotic behavior $$f(t)\approx A_{\alpha}\cdot\left(\dfrac{\tau}{t}\right)^{1+\alpha},t\to+\infty,0<\alpha<1$$ show that: ...
0
votes
3answers
40 views

Notation for asymptotic approximation

I was reading Stirling's approximation and got quite confused with the idea of asymptotic formula. So in Wikipedia it says that a function $F(n)$ of $n$ is asymptotic formula for $P(n)$ if $P(n)$ is ...
-1
votes
2answers
42 views

A function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$

Determine a function whose graph has vertical asymptotes at $x=+2$ and $x=-2$, and a horizontal asymptote at $y=0$? I don't know to satisfy these conditions.
0
votes
0answers
10 views

Which is the greatest integer value of $a$, for which $A'$ is asymptotically faster than $A$?

The recurrence relation $T(n)=7T\left( \frac{n}{2}\right)+n^2$ describes the execution time of an algorithm $A$. A "competitor" algorithm, let $A'$, has execution time $T'(n)=aT'\left( \frac{n}{4} ...
0
votes
0answers
41 views

Check if $2^{2^n}=O(2^n)$

I want to check if $2^{2^n}=O(2^n)$. That's what I have tried: Let $4^n=O(2^n)$. Then, $\exists c_1>0, n_1 \in \mathbb{N}$ such that $\forall n \geq n_1$: $$4^n \leq c \cdot 2^n$$ $$$$ ...
0
votes
1answer
33 views

How can we show that $\lim_{n \to +\infty} f(n)=+\infty$?

We suppose that $\lim_{n \to +\infty} f(n)=+\infty$. I want to prove that if $f(n)=O(g(n)), c \in \mathbb{R}$, then $f(n)+c=O(g(n))$ . $f(n)=O(g(n))$ That means that $\exists c_1>0, n_2 \in ...