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

learn more… | top users | synonyms (1)

7
votes
3answers
143 views

Asymptotic for sum

How can I find formula for $\displaystyle{\sqrt[3]1 + \sqrt[3]2 + \sqrt[3]3 + \cdots + \sqrt[3]n}$ with an accuracy ${\rm O}\left(\, 1 \over \vphantom{\LARGE A}n^{5}\,\right)$ Is here we should use ...
1
vote
1answer
21 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
1
vote
2answers
50 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
0
votes
0answers
10 views

Asymptotics and function composition

In the following question: Big O and function composition It is explained that if $a, b, c, d$ are functions and $a = O(c), b = O(d)$ it doesn't mean that $a ∘ b = O(c∘d)$. However, what if we allow ...
5
votes
2answers
351 views

Inverse of sparse matrix is not generally sparse

I have a question regarding inverse of square sparse matrices(or can be restricted to real symmetric positive definite matrices). I encountered several times the web pages which states that the ...
3
votes
0answers
39 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
0
votes
0answers
8 views

GRAM series and Logarithmic integral

due to the prime number theorem wouldn't we expect that the prime number counting function admits the approxiamtion $$ \pi (x)= \gamma +loglog(x)+ \sum_{n=1}^{\infty} \frac{log^{n}(x)}{n.n!.\zeta ...
2
votes
1answer
53 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
1
vote
0answers
34 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
0
votes
0answers
23 views

Big-O Notation Division

There was a similar thread on this question, but I am still unsure about the answer. I am asked to show, $$ \frac{e^{(r-q)h}-e^{-\sigma\sqrt{h}}}{e^{\sigma\sqrt{h}}-e^{-\sigma\sqrt{h}}} = ...
0
votes
0answers
13 views

What are asymptotic upper and lower bounds for $T(n) = T(n-2) + 1/\lg n$?

What are asymptotic upper and lower bounds for $T(n) = T(n-2) + 1/\lg n$? As $T(n)$ is not applicable for Master theorem,so i go ahead with the recursion tree but there i am not able to solve for ...
6
votes
1answer
345 views

Evaluating a limit of the truncated exponential series motivated by the prime number theorem for $k$ distinct prime factors.

If $\pi_k(n)$ is the cardinality of numbers with k factors (repetitions included) less than or equal n, the generalized Prime Number Theorem is: $$\pi_k(n)\sim \frac{n}{\ln n} \frac{(\ln \ln ...
2
votes
1answer
80 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
0
votes
0answers
30 views

Sort functions by their growth rate

So yesterday I had a mock exam and I failed an exercise. I'm trying to solve it but I definitely can't reach the solution. Here's the problem : Arrange the following functions in a list, so that ...
-1
votes
1answer
22 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
0
votes
0answers
15 views

Big theta question

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = 1^{(n^2+200n+5)}$. I worked out that $a = 1$ and that $1^{(n^2+200n+5)} \le C * 1^n, C = 1, n = 0.$ So long as n $\ge$ 0 the right-hand side ...
0
votes
1answer
17 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
0
votes
2answers
43 views

Why is Wolfram missing so many oblique asymptotes? (Not only about Wolfram in thread)

Few days ago I made a post, and to be frank I'm not sure if I'm even having this question in the right forum. But I'm also looking for information on if my thoughts are correct. Observe this little ...
0
votes
1answer
34 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
0
votes
3answers
57 views

Finding the limit of: $\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$

$\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$ I just removed a lot of unnecessary text from this post. If anyone could tell me how to find this limit, without L'Hôpital's rule, ...
1
vote
2answers
75 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: ...
3
votes
1answer
23 views

Oblique asymptote for: $f(t) = \frac{t^2\arctan t}{t-4}$?

Say a function $$f(t) = \frac{t^2\arctan t}{t-4}$$ Obviously, this has a vertical asymptote at $t = 4$. However, the oblique asymptote, if there is one, I can't seem to find. What I do is I put the ...
1
vote
1answer
35 views

Calculate the leading order asymptotic behaviour (with two maxima)

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
1
vote
1answer
38 views

Asymptotic solution to a differential equation near zero

I am trying to get the both the asymptotic solutions of the equation $y''(x)=\sqrt{x} \cdot y(x)$ as $x\rightarrow 0$. But when I put $y(x)=\exp(S(x))$ since $x=0$ is an irregular singular point, no ...
0
votes
1answer
22 views

How to prove this asymptotic bound? [closed]

Given that $0<a<b$, $f(n) \in O(n^a)$, prove that $f(n) \in o(n^b)$ (note there is a difference between big o and little o)
0
votes
0answers
11 views

Determining if f(n) is Big-O of g(n)

I'm currently learning Big-O notation but I'm having a lot of trouble understanding it. I'm working through some true/false exercises: 1) $log(k)$ is $O(k)$ 2) $klog(k)$ is $O(k^2)$ 3) $k^2$ is ...
2
votes
0answers
24 views

Number of ways to visit each cell of $n\times n$ board once

A piece lies on the upper-left corner of an $n\times n$ board. Let $f(n)$ denote the number of ways to move the pieces one step horizontally/vertically at a time, so that it visits each field of the ...
0
votes
3answers
55 views

Iterated integer-valued decimation

This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten. I am interested in really good upper bounds on the length of a ...
0
votes
1answer
27 views

Lower bounds for an expression of two positive integers?

Can we get an approximate lower bounds for the following expression: $$\left( 1 + \frac{1}{ 2 \left( \frac{4^{nC}-1}{2^n-1} \right) } \right)^{ \frac{1}{\left( \frac{4^{nC}-2^{nC}}{2^n-1} \right) } ...
2
votes
1answer
36 views

Asymptotics of $\frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $

Define $$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$ where $\mu()$ is the Möbius function. Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq ...
0
votes
2answers
38 views

Show that $3n^2 - n+4$ is $O(n^2)$

From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$. Substituting ...
0
votes
1answer
82 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
1
vote
0answers
25 views

Calculate the leading-order asymptotic behaviour (Laplace's Method) [duplicate]

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
2answers
15 views

Determine the asymptotic behavior of $f(n)$ in relation to $g(n)$

$f(n)=n^\sqrt{n}, g(n)=2^n$ $f(n)=10^{\log\log n}, g(n)=\log n$ Note: $\log$ is in base 2. For section #1, I tried to evaluate the limit $\lim_{n\to\infty} \frac{2^n}{n^\sqrt{n}}$ but got stuck ...
1
vote
0answers
24 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
0
votes
0answers
27 views

Am I to place my trust in Wolfram on this matter? [Oblique asymptotes on a function]

So I used Wolfram to find oblique asymptotes for the following function $f(x) = 2x + 3 - \frac{1}{\ln x}$ The vertical asymptote, which Wolfram finds as well, is $x=1$. However, my method for finding ...
2
votes
3answers
424 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
1answer
84 views

Find asymptotics in a given form $n=(e+o(1))^{f(s)}$

Let $p\to\infty$, $s={\binom {p^4} p}$ and $n={\binom {p^4}{p^2}}$. Find a function $f(s)$ in the following form $$\large n=(e+o(1))^{f(s)}$$ I've tried to use the followinf asymptotics for ...
1
vote
1answer
610 views

Asymptotic Matching for boundary layer problem

The question asks to find a global approximation to the leading order of $\epsilon$. $\epsilon y'' + xy' + \epsilon y =0$, with boundary conditions $y(0)=1,y(1)=-1$. I assumed it's a boundary layer ...
0
votes
1answer
263 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
1answer
37 views

Disproving a relation between function and derivative concerning Big-O-Notation

The question is to disprove the following: Be $f$ a continuously differentiable function that maps from $\mathbb{R}\rightarrow\mathbb{R}$ and $f(x) =\mathcal{O}(x^2) $ for $x\rightarrow0$, then it ...
0
votes
1answer
55 views

$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$) $$ \frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$ ...
1
vote
2answers
61 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
2
votes
1answer
37 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
0
votes
1answer
29 views

Prove that $\log^\alpha n = o( a^n )$

Please, how to prove: $\forall c \in \mathbb R_+$ $\exists n_0 \in \mathbb N_+$ $\forall n \ge n_0 :$ $log^\alpha n < c \cdot a^n$ for $ \\a>1$, $\alpha \in \mathbb R$ ? Thanks
0
votes
1answer
27 views

Solving $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ using Akra-Bazzi

I was trying to apply Akra-bazzi to solve $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ but I was having some issues. I was told that the correct way to solve it to express the floor in the form (for ...
0
votes
0answers
11 views

Asymptotic power series of $F(x)= \int_{0}^{T} f(t) e^{-xt}dt $

Let $f \in C^{\infty}$ and $T>0$. I am asked to find an asymptotic power series of the funtion: $$ F: \mathbb{R}_{+} \rightarrow \mathbb{R}, \quad F(x)= \int_{0}^{T} f(t) e^{-xt}dt$$ as $x ...
0
votes
0answers
23 views

Binomial series using gamma function

I am trying to find a formula of this online but am having a lot of trouble. In my textbook (Bender and Orszag), they make the following transformation for small $t$: ...
0
votes
0answers
38 views

Can $O(nd\log(d)) + O(n^2d) + O(n^3)$ be simplified?

Can $O(nd \log(d)) + O(n^2 d) + O(n^3)$ be simplified without increasing the time complexity? Can $O(nd \log(d)) + O(n^2 d)$ become $O(n^2 d \log(d))$? Can it all become $O(n^3 d \log(d))$? Please ...
0
votes
1answer
16 views

Limit of multivariate polynomial with large arguments

If I have a polynomial $f(x,y)=x^4+y^4-4xy$, how would I go about showing that as the standard norm of $(x,y)$ goes to infinity, $f(x,y)$ goes to infinity?