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
152 views

How to determine a $\Theta$-class of a Function

I have 6 functions that I have to determine which of 4 given $\Theta$-classes or neither of them. Example of a function I have been given: \begin{align*} \textit{$f_1$}(n) =&(17\textit{n}+1) \\ ...
0
votes
1answer
154 views

Does the sum of reciprocals of the harmonic divisor numbers converge?

Does the sum of reciprocals of the harmonic divisor numbers converge? Define the following: Harmonic divisor number - $n$ such that $\sigma(n) \mid n\sigma_0(n)$. Equivalently, the harmonic mean of ...
6
votes
1answer
63 views

Asymptotic behaviour of sum of decreasing definite integrals

I would like to calculate: \begin{equation*}g(K, T) = \displaystyle \sum_{k=1}^{K} \sum_{t = 1}^{T} \int_{0}^{1} \left(1 - z^k\right)^t \, dz. \end{equation*} If no closed form solution exists, I ...
0
votes
2answers
778 views

How does adding big O notations works

can someone please explain how adding big O works. i.e. $O(n^3)+O(n) = O(n^3)$ why does the answer turn out this way? is it because $O(n^3)$ dominates the whole expression thus the answer is still ...
0
votes
0answers
703 views

D ary tree node math

A d-ary tree is a rooted tree in which each node has at most d children (c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your ...
1
vote
1answer
86 views

base transformation rule significance in finding big o notation

Recall the equivalence: $$m=b^k \implies k = log_bm$$ as well as the base transformation rule: $$log_am=(log_ab)(log_bm)$$ Are the following true or false? (a) $log_2n$ is $O(log_3n)$ (b) ...
2
votes
4answers
2k views

Prove that $3^n$ is not $O(2^n)$

I have this question in my assignment. I need to prove, using only the definition of $O(\cdot)$, that $3^n$ is not $O(2^n)$. It is obviously true for any $n \geq 1$. To prove $3^n \in O(2^n)$, we ...
1
vote
2answers
195 views

Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

I've been trying to find tight bounds for the equation: $$ T(n) = 2T(n/2) + n/\lg{n} $$ The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that ...
-1
votes
1answer
330 views

Logarithms and big O notation

Recall the equivalence: $$m=2^k \implies k=log_2m$$ (a) Consider the sequence: $a_1=1, a_{k+1}=2a_k$ what is the smallest k for which $a_k \geq n$? Your answer should be a function of n, and you can ...
0
votes
1answer
96 views

Big theta for a S(n)

Consider the following function: $$S(n)=1+c+c^2+⋅⋅⋅+c^n,$$ where c is a positive real number. (A) This function is the sum of a geometric series. Give a precise closed-form formula for S(n), interms ...
3
votes
1answer
94 views

Showing an approximation is uniformly asymptotic

I am trying to show that the approximation on $0\leq x \leq 1$ $$\phi(x,\epsilon) \sim \sin x+ \epsilon \cos x - \epsilon$$ is uniformly asymptotic to the exact solution $$f(x,\epsilon) = ...
7
votes
1answer
149 views

Approximate $\int_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$

I am trying to approximate the following integral $$K(x)=\int\limits_0^{\pi /2} \frac{ds}{\sqrt{1-x\sin^2s}}$$ with $0<x<1$. I need to show that for x close to one that $K(x)\sim ...
2
votes
1answer
205 views

Why does $af(n/b) <= cf(n)$ for $c < 1$ imply that $f(n) = \Omega(n^{\log_ba+\epsilon})$?

The Master method for solving recurrences of the kind $T(n) = aT(n/b) + f(n)$ has a third case, which requires a regularity condition to hold: $$ af(n/b) \le cf(n) \qquad a \ge 1, b > 1, c < ...
0
votes
2answers
1k views

Big O notation for summation

Consider the summation $$S(n)=1^c+2^c+3^c+...+n^c,$$ where c is some fixed positive integer. (a) Show that $S(n)$ is $O(n^{c+1})$ I did this part the following way, $S(n)$ is $O(n^{c+1})$ because ...
2
votes
2answers
369 views

Big O and Omega Properties

I am trying to think of a case where this is not true: $f(n) = O(g(n))$ and $f(n) \neq \Omega(g(n))$, does $f(n) = o(g(n))$? I suspect that it has to do with the varying $c$ and $n_{0}$ constants ...
0
votes
1answer
281 views

Does log $f(n) = O($log $g(n))$ imply $f(n) = O(g(n))?$

Assuming log is base 2, if I know that: log $f(n) = O($log $g(n))$. Does this imply that $f(n) = O(g(n))$? I understand that the converse is true.
0
votes
1answer
77 views

Time Complexity involving a conditional f(n) when n is even and odd

Trying to find an asymptotic relationship between: $f(n)$ and $n^2$ where $f(n)$: if n is even, $f(n) = 8n$. if n is odd, $f(n) = 5.5n^2$. Not sure how to approach when the function is ...
2
votes
1answer
57 views

Comparing time complexities

I'm trying to understand which of the following functions is strictly faster growing ($\Omega$, $o$-notation or $\theta$-notation). Not sure how to approach the following equations: $$\bf{n^{0.3} \ ...
0
votes
1answer
1k views

Geometric series and big theta

Consider the following function: $$S(n)=1+ c + c^2 + ··· + c^n,$$ where c is a positive real number. (A) This function is the sum of a geometric series. Give a precise closed-form formula for ...
1
vote
1answer
132 views

GCD = 1 and harmonic numbers, what is the exact asymptotic?

I am looking for the exact asymptotic for this partial sum: $$a(N) = \sum_{n=1}^{n=N}\sum_{k=1}_{GCD(n,k)=1}^{k=n*m} \frac{1}{k}$$ where $m$ is some integer $1,2,3,4,5,...$ My guess was that since ...
4
votes
1answer
127 views

Prove Linearity in Asymptotic Notation

The question: Prove O($\sum\limits_{k=1}^m(f_k(n))$) = $\sum\limits_{k=1}^m(O(f_k(n)))$ What I have done so far: Left side: Let g(n) = O($\sum\limits_{k=1}^m(f_k(n))$) For n > c, we have g(n) $\le$ ...
2
votes
1answer
917 views

How to find $\frac{n^3}{1000} - 100n^2 - 100n + 3$ in terms of Θ and prove it?

Question: Express the function $\frac{n^3}{1000} - 100n^2 - 100n + 3$ in terms of the Θ notation and prove that your expression in fact fits into the Θ definition. So far I have, $n^3 / 1000 - ...
2
votes
0answers
87 views

Asymptotic of Stirlings numbers of the first kind

I am trying to find some asymptotic expression for the unsigned stirling numbers of the first kind. Lets denote them by $|s(n,k)|$, and suppose that $k$ is fixed. So far I have tried using the fact ...
10
votes
1answer
133 views

Find asymptotic of recurrence sequence

Given a sequence $x_1=\frac{1}{2}$, $x_{n+1}=x_n-x_n^2$. It's easy to see that it limits to $0$. The question is: is there exists an $\alpha$ such, that $\lim\limits_{n\to\infty}n^\alpha x_n\neq0$. ...
0
votes
0answers
57 views

Asymptotic for Taxicab number.

The taxicab numbers are sums of 2 cubes in more than 1 way. First few are - 1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728, 110656, 110808, 134379, 149389, 165464, 171288, ...
1
vote
1answer
76 views

Prove $T(n) = 2T(\frac{n}{2} - 3) + n$ is $O(n\lg n)$

I just had an exam in my algorithms class and this was a question on it. I was able to craft a solution, but I'm not sure if my proof has errors. $$\begin{align} &\frac{n}{2}-3 < n & ...
2
votes
3answers
154 views

Bernoulli numbers: comparison to factorials

I am trying to understand the behaviour of the Bernoulli numbers with respect to factorials, specifically I'd like to know whether it is true that, for all $n \in N$ with $n \ge 2$ we have $$ ...
2
votes
1answer
83 views

Asymptotic expansion of $(1+\frac{t}{n})^{-n-1}$ at $n \to \infty$

I'm reading through a proof in Analytic Combinatorics by Flajolet/Sedgewick and I have come across this: We have the asymptotic expansion: ...
1
vote
1answer
1k views

Proving that $3n^2 + n \log_2n - 2$ is $\Theta (n^2 - 5n +1)$

Specifically the following: $3n^2 + n \log_2n - 2 \in \Theta (n^2 - 5n +1)$ I'm aware it needs to be $g(n)c_1 \le f(n) \le g(n)c_2$, where $g(n)$ is $\Theta (n^2 - 5n +1)$ and $f(n)$ is $3n^2 + n ...
-1
votes
1answer
40 views

Finding $k$, $C_1$, and $C_2$ when $f(x)$ is $Θ(g(x))$

How can I find the constants $k$, $C_1$, and $C_2$ when I know that $f(x)$ is $Θ(g(x))$? $f(x)=3x^2+x+1$ and $g(x)=3x^2$ I have that $C_1g(x) \le f(x) \le C_2g(x)$ $C_1 \le \frac{f(x)}{g(x)} \le ...
2
votes
1answer
42 views

Would this be bounded

Let $a_{m}$ be supremum of the minimum of the angle between the line segments between any $m$ points, in which the supremum is taken over all configurations of $m$ points. Is $\sqrt{m}a_{m}$ bounded ...
1
vote
1answer
183 views

Running time of a function of n with while loop

Provide a tight Θ bound on the running time of the function of n. ...
1
vote
1answer
70 views

What is the difference between $O(N/ \log_2(N))$ and $N-o(N)$?

On the second page of this paper under the introduction section they say "We first show that for the set of parameters considered by [16], the function family has $O(N/ \log_2(N))$ simultaneously ...
2
votes
2answers
62 views

Running time of a function of n

Provide a tight Θ bound on the running time of the function of n. for a=1 to n for b=1 to lg(n) for c = 1 to 23 x = 2x My thinking in solving ...
4
votes
4answers
258 views

Taylor series of $\arctan(x+2)$ at $x=\infty$

The simple question is: what is the correct way to calculate the series expansion of $\arctan(x+2)$ at $x=\infty$ without strange (and maybe wrong) tricks? Read further only if you want more details. ...
1
vote
3answers
1k views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
150 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
1
vote
1answer
61 views

Growth rates that follow : $f(n) \not\in Og(n)$ and $g(n) \not\in Of(n)$

Ok so the problem I am interested in is $f(n) \not\in Og(n)$ and $g(n) \not\in Of(n)$ dealing with natural numbers into positive reals, ($\mathbb{N}$ $\rightarrow$ $\mathbb{R+}$ ) O is a comparison ...
1
vote
1answer
70 views

What exactly is a multi-scale operator and what does it do?

In a paper I'm reading at the moment we're concerned with a third order nonlinear ODE for which we know the solution near thr origin look something like an upside-down parabola crossing the y axis at ...
1
vote
1answer
64 views

Big-O Example question

Could you please give an example that disproves the following Big-O comparison: $$f(n)^2=O(g(n)^2)\qquad\text{implies}\qquad constant^f=O(constant^g)$$
0
votes
1answer
187 views

Prove or counterexample: $f(cn) \in \theta (f(n))$

Prove or provide a counterexample: For every positive constant c, and every function f from nonnegative ints into nonnegative reals, $$f(cn) \in \theta (f(n))$$. At first, I thought this was obvious, ...
6
votes
1answer
71 views

Are there asymptotically more nonabelian groups of order $p^k$ than there are abelian groups of order $\leq p^k$?

Let $\alpha(n)$ denote the number of isomorphism classes of abelian groups of order $n$ and $\alpha^\prime(n)=\sum_{m=1}^n\alpha(m)$. Similarly, define $f(p^k)$ to be the number of isomorphism ...
0
votes
3answers
103 views

Asymptotic of binomial coeficient

I was doing a problem, and I found that I needed to calculate asymptotics for $$ \frac{1}{{n - k \choose k}}$$ Supposing $n = k^2$. Any help with this would be appreciated, thanks.
0
votes
2answers
112 views

Using the definition of Θ prove or disprove the following:

$$ \dfrac{4n^4 -18n^3 +3n^2 -660}{n^2 +560n -1024} = Θ(n^2) $$ It's been quite a while since I've one this as a ratio and I'm a bit lost on what steps to take for this. I know we'll need to prove ...
0
votes
1answer
385 views

Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$

I believe that my understanding of this question is incorrect, so any help would be appreciated. The Question: Prove: $\theta(n^2)+O(n^3)\subset O(n^3)$ Note that for this problem, you are proving ...
2
votes
2answers
424 views

Using Master's Theorem with $f(n) = \lg^2 (n)$

This is a homework question about using Master's theorem, and I can't seem to wrap my head around this question: $$T(n)=2T\left(\frac{n}{3}\right)+\lg^2(n)$$ I've tried to apply the Master's ...
0
votes
1answer
38 views

Asymptotic coefficients of generating function $\frac{F(z)}{G(z)}$

I have the OGF in form of $\frac{F(z)}{G(z)}$, both $F(z), G(z)$ are polynomial expression and relatively prime. Do we have the systematic way to estimate $[z^n]$? I know that we can estimate ...
0
votes
2answers
750 views

Proof of $\Theta (n^2) + O(n^3) \ne O(n^3)$

This is a homework question. I have proved before that the sum of the terms on the left-hand-side are a subset of $O(n^3)$, but I have not proved that the two terms are not equal (or whether that was ...
0
votes
1answer
45 views

Analysis of the limiting behavior of a certain expression

Apologies in advance if this is too easy of a question, but as an engineer, I am out of my depth. I am interested in the conditions under which the following expression approaches to $0$: $$1 - ...
1
vote
1answer
84 views

Asymptotic bounds. What software to use?

For a pair of expressions ($A,B$), I need to determine whether $A$ is upper asymptotic, tight bound, or lower asymptotic of $B$. For example: $$A = n^{\log(c)}$$ $$B = n^{sin(n)}$$ What (free) ...