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

learn more… | top users | synonyms (1)

2
votes
0answers
41 views

Asymptotic behavior of $1/(a^2+\epsilon^2)$ as $\epsilon\to0$

A limit that often arises in physics is $$ \lim_{\epsilon \to 0} \frac{ \epsilon }{ a^2 + \epsilon^2 } = \pi \delta(a) ............ (1) $$ Is there a similar sort of limit for $$ \lim_{\epsilon \to 0} ...
2
votes
4answers
139 views

Limit and infinite sums. Finding $\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\frac{1}{k^3 x-k^2}$

Could anyone help me with this problem. Compute $$\lim_{x\rightarrow\infty}\sum^{\infty}_{k=1}\dfrac{1}{k^3 x-k^2}$$ I don't know how to change a limit and a sum. Could you help me with this problem ...
0
votes
1answer
252 views

Use recursion tree to give an asymptotically tight solution of T(n)

Assume $T(1) = 3.$ Recurrence is $T(n)=T(n-3)+3n+1$ and I'm showing $\Theta$ bound by computing the exact running time. Starting off: $(Tn-3) + 3n + 1$ $(Tn-9) + 9(n-3) + 3n + 1$ $(Tn-18) + ...
0
votes
1answer
139 views

Tight bound for $T(n) = T(n^{1/2}) + 1$ [duplicate]

Can someone help me figure out the big-O for the recurrence relation $T(n) = T(n^{1/2}) + 1$? I didn't think the master theorem would work since it requires $T(n) = T(n/b)$... to have $b$ as a ...
0
votes
1answer
149 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
1
vote
1answer
104 views

Growth faster than polynomial, slower than exponential.

Assume $F(n)$ is a positive function. If $F$ is growing faster than a polynomial then is it growing exponentially fast? Is this statement true? Can we find a function $F(n)$ such that ...
0
votes
0answers
21 views

Limit of shifted ratios

Let $f$ a be a strictly positive function defined in the positive reals. Additionally suppose that for any $\delta > 0$ we have, as $t \to \infty$, $$ e^{-t^{1+\delta}} \ll f(t) \ll ...
0
votes
2answers
37 views

How to justify adding and multiplying relations with big-O?

I know that it's valid to add and multiply functions in Big O, although I haven't seen a proof why. As such I think this is a valid starting point. However, I have no idea how to progress and any help ...
0
votes
1answer
39 views

Show the correctness: $\log^3( n)\in o(n^{0.5})$

show the correctness: $\log^3 (n)\in o(n^{0.5})$? I started from this way $$\log \log \log( n) = n^{0.5}$$ then I take $\log$ for two parties $$\log\log\log\log( n) = 0.5 \log( n)$$ ...
3
votes
0answers
47 views

Algorithms - Solving the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ [duplicate]

I have been trying to solve the recurrence $T(n) = \sqrt{n} T \left(\sqrt n \right) + n$ for some time now. I only know substitution, recursion trees, and the master method (though it doesn't apply ...
1
vote
1answer
179 views

Proving that one function is big o of another?

I'm working through a big-O problem and have the intuition to know the answer, but don't feel comfortable in my proof. I need to prove from definitions (i.e. proving that there exists two constants ...
3
votes
0answers
93 views

Effect of differentiation on function growth rate

For sufficiently "nice" functions, the differentiation operator appears to make slow growing functions grow slower and fast growing functions grow faster, with $e^x$ as a fixed point in the middle. ...
0
votes
0answers
259 views

Implicit function where the Jacobian determinant is zero

When we have an implicit function defined by $f(x,y)=0$ where Jacobian determinant of $\frac{\partial f}{\partial x}$ is zero Let $x \in \mathbb{R}^n$, $p \in \mathbb{R}$ and $\phi:\mathbb{R}^n \to ...
1
vote
1answer
98 views

How to solve this triple summation problem?

For a computer science class we were asked to analyze the run time of an algorithm. The answer was posted. I am not sure the proof is correct. I believe the answer should be kc(n^2) (where k is a ...
0
votes
1answer
1k views

Determine the number of paths of length 2 in a complete graph of n nodes

Question: Determine the number of paths of length 2 in a completed graph of n nodes. Give your answer in Big-O notation as a function of n So I started working on this problem however I know im doing ...
2
votes
2answers
98 views

Proof $10n = O(n^2)$

As it says in the question name. I want to proof this big-o notation: 10n = O(n^2) Is this way here the correct an proper way to do so? ...
1
vote
1answer
22 views

Showing $\limsup_{h \to {0}}\frac{O(h^2)}{h^2}<\infty$

Let $$y(h)=1-2\sin^{2}(2\pi h) , f(y)=\frac{2}{1+\sqrt(1-y^2)} $$ Justify the statement $$f(y(h))=2-4\sqrt{2}\pi+O(h^2)$$ where $$\limsup_{h \to {0}}\frac{O(h^2)}{h^2}<\infty$$
0
votes
1answer
33 views

Big-O of a Function

Given $F(N) = 55N(600 + 50N \log N + 20N) + 20N(30N + 20\sqrt N)(50 + \log N)$. How can one combine multiplication with addition for a Big-O estimate by algebraic means? I'm used to simply taking the ...
2
votes
0answers
31 views

Relationship between asymptotic distribution and logarithmic sums of elements of subset of the natural numbers

Consider a subset $A$ of the natural numbers analogous to the primes (but rarer). Let $a_n$ denote the $n$th element of $A$, and $a(n)$ denote the number of elements of $A$ less than or equal to $n$ ...
1
vote
2answers
57 views

Big $O$ — $3^n$ vs $n2^n$

I'm trying to compare $f(n) = 3^n$ and $g(n) = n2^n$ to determine whether $f \in O(g)$, $f \in \Omega(g)$, or $f \in \Theta(g)$. My gut is telling me that $g(n) = n2^n$ grows faster, and so $f \in ...
1
vote
1answer
67 views

Proof $(\log(n))^{\log(\log(n))} = O(n)$

Can someone provide a proof that $(\log(n))^{\log(\log(n))} = O(n)$? Preferably without calculus, but I'll take what I can get. Just ran into this problem, and I have no way of moving forward, ...
2
votes
1answer
71 views

What is the point of big Oh notation when it is used for estimation?

I'm reading a book on number theory at the moment that assumes familiarity with big Oh notation...and while I think I do understand the notation I cannot understand the point of it. For instance let ...
1
vote
2answers
58 views

Is $\lceil{\lg n}\rceil!$ polynomially bounded?

Is $\lceil{\lg n}\rceil!$ polynomially bounded? I've tried using Stirlings Approximation, and I get that $\lceil{\lg n}\rceil! \approx \sqrt{2\pi}\lceil{\lg n}\rceil^{1/2}\lceil{\lg n}\rceil^{\lceil ...
0
votes
1answer
46 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
2
votes
1answer
41 views

Asymptotic formula for sums related to primes

Suppose $0 < \alpha < 1$. What is the asymptotic formula for the sum $$\displaystyle \sum_{p \leq x} \frac{\log p}{p^\alpha}?$$ Thanks for any insights.
0
votes
1answer
31 views

summation inequality with logarithms

show: $$\sum_{i=1}^n \log_{2}\,i = O(n\log n)$$ Proof by induction: $$\sum_{i=1}^n \log\,i \le n\log n$$ $$\text{Test for n=1: }\sum_{i=1}^1 \log_{2}\,i \le 1\log 1$$ $$0 \le 0\text{ true for ...
1
vote
1answer
94 views

Determine whether each pair is $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)).$

For the pair of functions, find whether it's $f(n) = O(g(n), f(n) = \Omega(g(n)), or f(n) = \Theta(g(n)):$ $a) f(n) = 12^n , g(n) = 7^n$ $b) f(n) = log_9(n^4), g(n) = log_9(n^5)$ I understand that: ...
0
votes
1answer
44 views

Need explanation on asymptotic running time results for various functions

I did not understand few results from the book problem. Here is the problem: Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, ω, Θ of B. Assume that k ≥ 1,  > ...
0
votes
2answers
94 views

Proof by induction summation inequality: $\sum_{i=1}^n i^2 = O(n^3)$

show by induction that: $$\sum_{i=1}^n i^2 = O(n^3)$$ what I have so far: $$\sum_{i=1}^n i^2 \le n^3$$ base case: for n=1 $$\sum_{i=1}^1 i^2 \le 1^3$$ ...
3
votes
2answers
161 views

Higher Order Terms in Stirling's Approximation

Some websites and books give stirling approximation as $$n! = \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \left( 1 + O \left(\frac{1}{n} \right)\right)$$ However when I check their derivations most ...
-3
votes
1answer
61 views

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$?

If $f(n)$ is not $\Theta (g(n))$ does it follow that $\log f(n)$ is not $\Theta(\log g(n))$? We say that $f(n)= \Theta (g(n))$ if there exist some constants $c_1$ and $c_2>0$ and $n_0$, such ...
0
votes
1answer
61 views

Solving recurrence relations using master's theorem

Can we solve following recurrence relation using Master's theorem- $T(n)=T(n/2)+\log n$ The thing to notice here is that, do $n (n^{\log b} a)$ and $\log n (f(n))$ have an exponential ...
2
votes
1answer
84 views

Asymptotics of $\sum_{\mathfrak{a}}\frac{n^{k-\epsilon}}{\mathfrak{N}\left(\mathfrak{a}\right)^{r\left(k-\epsilon\right)}}$

In this paper by Brian D. Sittinger, the following claim is made: For an algebraic number field $K$ with norm $\mathfrak{N}$, let $\epsilon=\left[K:\mathbb{Q}\right]^{-1}$. Then, taking the sum over ...
1
vote
0answers
118 views

Compute the asymptotic expansion of the integral by Watson's Lemma

Use Watson's Lemma to find the asymptotic expansion of the following integral as $\lambda \to \infty$ with $\lambda>0.$ Assuming that $\phi (t)$ is infinitely differentiable on $[0,1].$ ...
1
vote
0answers
16 views

Calculating Upper bound of a function [duplicate]

If T(N) = T(sqrt(N)) + 1 and T(1) = 1 then what is the upper bound i.e O(N) for this function? sqrt(N) => square root of N
2
votes
1answer
65 views

Asymptotics of $\sum_{n\leq x}\tau_{k}\left(n\right)$

We define $\tau_{k}\left(n\right)$ to be the number of ordered $k$-tuples of positive integers with product equal to $n$. It is easily shown that this satisfies the recurrence relation ...
3
votes
2answers
98 views

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation.

Prove that $7n^2 + 2n + 3 = O(n^2)$ using the definition of O notation. I need to use two constants and prove that they satisfy the O definition. I'm new to big O and want to know whether I am ...
3
votes
1answer
70 views

What proportion of the positive integers satisfy this number-theoretic inequality?

Let $\sigma(x)$ be the sum of the divisors of the positive integer $x$, and let the abundancy index of $x$ be defined as $$I(x) = \frac{\sigma(x)}{x}.$$ My question is this: What proportion of the ...
3
votes
2answers
622 views

Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$

I'm trying to solve the following problem: Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$. Is $T(n) \in \mathcal O(2^n)$? I started by finding the time complexity of $T(n) = n\cdot T(n-1) + ...
1
vote
1answer
37 views

Series involving primes

Trying to find an asymptotic bound for the series $$ S(x) =\sum_{p\leq x}\frac{\varphi(p-1)}{(p-1)p} $$ as $x \rightarrow \infty$. Of course $$ \frac{\varphi(p-1)}{p-1} =\prod_{q\mid ...
0
votes
2answers
88 views

Big-O math Question

I'm having trouble with this question: Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$. I have tried ...
2
votes
3answers
124 views

Proving with Big O Notations

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?
0
votes
1answer
383 views

Big O Proof by Contradiction

Question: Use a proof by contradiction to show that $5^n$ is not $O(3^n)$ NOTE: This is homework, please don't provide an answer, just want to know if I am on the right track. My Attempt: ...
1
vote
2answers
48 views

Understanding the logic behind this summation

The following is an excerpt from a proof that $\sum_1^n {i^k} = \theta(n^{k+1})$: $$\sum_1^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{i^k} \ge \sum_{\lceil n/2 \rceil}^n{\lceil n/2\rceil^k}$$ The first ...
1
vote
1answer
46 views

Showing $n^{\log{n}} = o(2^n)$

I would like to show that $n^{log n} = o(2^n)$. Here is my attempt: I see that $\log{(n^{\log{n}})} = (\log{n})^2,$ and $\log{2^n} = n\log{2}$. I also know that $(\log{n})^2=o(n)$, so that for ...
0
votes
1answer
11 views

Orders of Asymptotes

We know that $\log(X)^n = o(X^\epsilon)$ for all $n,\epsilon>0$. My questions is, is $\log(X)$ the largest function that is smaller than all (small) powers of $X$. That is, can we find a ...
1
vote
2answers
46 views

On finding the order of an infinitely small quantity

Given an infinitely small quantity: $$\alpha \left ( x \right )= \tan \left ( x \right )-\sin \left( x \right)$$ as x aproaches $0$, and computing the corresponding asymptotic relationship. What does ...
3
votes
2answers
68 views

Can we give a bound on any associative function?

We say that $f:[1,\infty)^2\to[1,\infty)$ is associative if $$f(f(a,b),c)=f(a,f(b,c))$$ And symmetric if $$f(a,b)=f(b,a)$$ e.g. the arithmetic operations '+' and '$\cdot$' are associative and ...
3
votes
3answers
105 views

How do I show that as $z \to \infty$ that $\int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} dt = O(z^{-1} )$??

How do I show that as $z \to \infty$ we have $$ \int_0^\infty \frac{t - \lfloor t \rfloor - 1/2}{z + t} \,dt = O(z^{-1} )? $$ According to Serge Lang, the integral on the left is the error term for ...
6
votes
2answers
110 views

Asymptotic form of the integral $\int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs}$ for $s \to \infty$

I would like to find an asymptotic form of the following integral when $s \to \infty$ ($s$ and $w$ are positive) \begin{equation} \int_{0}^{\infty} dx ~ \sqrt{x^2 + wx} ~ e^{-ixs} \end{equation} I ...