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
1answer
23 views

Time Complexity for Asymptotic Functions

Here below I have a problem set where I am asked to define the relationship between f(n) and g(n). I have added in my solutions but I wanted to get my answers checked by you guys before I turn this ...
1
vote
1answer
29 views

Confusion about Big O notation

I have a somewhat stupid question regarding the "Big O" notation: Is there any difference between saying $f=O(g)$ and $f\le O(g)$?
0
votes
0answers
39 views
0
votes
0answers
11 views

Linking summations with their correct function(s)

Guys can you please guide me step by step on how to link given functions with the functions to choose from. So for example a function $g(n)\in \Theta n^2$ and if there is no match then you say there ...
1
vote
1answer
19 views

Asymptotic Notation Analysis Problem

I'm new here. I have some question on asymptotic analysis I am trying to calculate the Big-O of these five functions and rank them up: a: $$2^{log(n)}$$ b: $$2^{2log(n)}$$ c: $$n^{5\over2}$$ d: ...
0
votes
1answer
34 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
41 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
34 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
41 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
18 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
1answer
23 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
34 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
48 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 ...
0
votes
0answers
15 views

Bound from distinct integer summation

We want to find $r$ positive integers $\{a_i\}_{i=1}^r$ such that of atmost $(s+1)^r$ values obtained from $$\sum_{i=1}s_ia_i$$ where $s_i\in\{0,\dots,s-1,s\}$, we insist on some combination of ...
3
votes
2answers
80 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 ...
0
votes
1answer
31 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 ...
0
votes
0answers
67 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
38 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 ...
5
votes
3answers
202 views

Use the Euler-Maclaurin summation formula to estimate a summation

$\sum_{k=0}^n \frac{1}{1+\frac{k}{n}}$ How can we estimate it to order $O(n^{-5})$ ?
2
votes
2answers
58 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$ that $\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 Stirling's ...
2
votes
2answers
96 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
2answers
144 views

$Θ(n) + O(n) = ?$ (recurrence equation)

If I have a recurrence equation like $$T(n) \leq T(n/2) + Θ(n) + O(n),$$ then is this expression equal to $T(n) \leq T(n/2) + Θ(n)$? Or is that expression equal to: $T(n) \leq T(n/2) + O(n)$?
1
vote
1answer
21 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
26 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 ...
1
vote
1answer
110 views

Density of primes in a polynomial

Consider that $p(x)$ is an irreducible polynomial with integer coeficients, that $\mathrm{gcd}$ of its coefficients is $1$. What is the natural density of the below set? $$A = \{n\ |\ p(n)\ \text{is ...
3
votes
1answer
58 views

Sum of squares of Binom(n,p) values

Let $x_{n,p}(j)$ be the probability that a random variable distributed according to a binomial distribution with parameters $n \in \mathbf{N}_+$ and $p \in (0,1)$ takes the value $j \in ...
2
votes
0answers
26 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
26 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
58 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
0answers
167 views

Big-O Notation for remainder terms in Taylor expansion

The Big-O notation is commonly used in Taylor expansions of the form $$f(x+\epsilon)=f(x)+\epsilon f'(x)+O(\epsilon^2)$$ to say that the remainder term grows at least quadratic around $\epsilon=0$. ...
2
votes
1answer
49 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 ...
0
votes
0answers
13 views

How to solve this kind of difference equation?

How to find $v_k$, $k=0,1,2,\dots$ such that $$v_k + \sum_{n=1}^{k} \frac{\alpha^n}{n}v_{k-n} + \sum_{n=1}^{k}\frac{\beta^n}{n}v_{k+n} = 0,$$ where $\alpha,\beta \in \mathbb{C}$. ($v_i=0$ for ...
2
votes
2answers
41 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) + ...
2
votes
1answer
61 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
2answers
36 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 ...
2
votes
1answer
36 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.
2
votes
2answers
377 views

Question about the “master theorem” of recurrences - no “$b$” term

I'm using the master theorem to find the asymptotic run time of recurrences. For example, for a $T(n) = 4 T(n/5) + n^1$ I find that $T(n)$ is $\Theta(n^1)$, or, simply, constant time, via the set of ...
1
vote
1answer
36 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
2
votes
0answers
44 views

Method of stationary phase for double integrals

I am looking for a reference for the leading term in the asymptotics of a double integral over a finite rectangle R of $K(x,y)\exp(i \,t\, h(x,y))$ as $t \to \infty$ in the following situation: the ...
3
votes
2answers
63 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 ...
0
votes
1answer
29 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 ...
0
votes
1answer
23 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
28 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
20 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
39 views

proof by induction summation inequality

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

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
11 views

Am I comparing big-O runtime correctly?

I'm working on some homework regarding runtimes and Big-O notation. I've struggled with this for quite some time, but I think its slowly making more sense. If someone could verify that I'm doing these ...
1
vote
1answer
32 views

Weyl's law, meaning of the asymptotic formula, does it imply a bound?

Weyl's law states the eigenvalues of the Laplacian behave as $$\lambda_j \sim f(n)j^{\frac 2n}\quad\text{as $j \to \infty$}$$ where $n$ is the dimension. Does this literally mean that, $$\lim_{j \to ...
-3
votes
1answer
46 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 ...
1
vote
0answers
42 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].$ ...