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

learn more… | top users | synonyms (1)

1
vote
1answer
122 views

Big O with Log base equivalences and a question about sum of series.

Hi I need help figuring these out: True or False: $\log_2 n$ is $O(\log_3 n)$ I used the definition of Big O in Dasgupta's book: ${f(n)}\over g{(n)}$ $\leq c$ So I used the base transformation rule ...
1
vote
1answer
143 views

When can we exchange the order of big/little O and function composition

From Wikipedia Let $f(x)$ and $g(x)$ be two functions defined on some subset of the real numbers. One writes $$ f(x)=O(g(x))\text{ as }x\to\infty\, $$ if and only there exists a ...
0
votes
1answer
200 views

How do you get the upper bound over this recurrence?

$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$ I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. ...
3
votes
1answer
245 views

“Proof” that if f(x) ~x, e^f(x) ~ e^x

While it is not true that $f(x)\sim x \implies e^{f(x)}\sim e^x,$ I can't spot the error in this "proof" by induction--or at least I can't articulate it well. Let $f(x)\sim x$ and $x > 1$ P(1): ...
0
votes
1answer
71 views

Is there an asymptote in this graph?

In the 2nd graph, is there an asymptote? Thanks!
0
votes
1answer
36 views

In these 2 graphs, is x=2 an asymptote?

Do these 2 graphs have asymptotes at x=2? http://puu.sh/1aihI In the second graph, IS THERE an asymptote? Thanks!
1
vote
2answers
37 views

Limit and asymptotics

How does $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0$ imply that $f(n) \in \mathcal{O}(g(n))$? I'm having trouble understanding that.
6
votes
1answer
159 views

Computing very high powers of a particular Jordan block

Let $J$ be the following $k-by-k$ Jordan block: $$ J:= \begin{bmatrix} e^{i \theta} & 1 & \\ & e^{i \theta} & 1 \\ & & \ddots & \ddots \\ & & & \ddots & ...
1
vote
1answer
118 views

Big-Oh of $\log (n^x)$

Prove that if $d(n) = \log(n^x)$, where $x$ is a constant greater than zero, then $d(n)$ is $O(\log(n))$. I have attempted this solution but it seems to me that $\log(a) > \log(b$) if $a > b ...
2
votes
1answer
37 views

Code Run Time Proof

TRUE or FALSE: For two positive functions $f(n)$ and $g(n)$, $f(n)$ has to be either $O(g(n))$ or $\Omega(g(n))$ or both. I feel like using $\sin$/$\cos$ for $f$ and $g$ would be a way of ...
1
vote
0answers
132 views

Approximation of distribution of $\pi_k(n)$ using $\zeta(s)$

Let $\pi_k(n) $ be the number of numbers with k prime factors (repetitions included) less than or equal to n. If we take the sums: $z_1(s) = \sum_{n= 1}^\infty \frac{1}{(p_{1,n})^s},~ z_2(s) = \sum ...
1
vote
2answers
318 views

Big O — mathematical Proof with a summation series

I am looking to prove that for every fixed value of $k$, $$ n^{k+1}= O(1^k + 2^k + \cdots + n^k) $$ I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the ...
2
votes
1answer
132 views

Master Theorem when B is a fraction.

So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball $T(n) = 4T(3n/4) + n^4$ Now I used my usual steps of listing out what A, B, ...
3
votes
0answers
72 views

How to explore the asymptotic of an iteration

Definition Given that $f:\Bbb R\to\Bbb R$ is a real-valued function. The iteration of $f$, say $f^n$, is defined here: $f^0(x)=x$ $f^n(x)=f\left(f^{n-1}(x)\right)$ for any positive integer $n$. ...
1
vote
1answer
277 views

Comparing asymptotic order of logarithmic functions

If I have two complicated logarithmic functions, say $\sqrt{\log n}$ and $\log(n(\log n)^3)$, and I have to compare them in terms of their asymptotic order. How do I do that? Do I have to create ...
2
votes
2answers
654 views

A function that is neither O(n) nor Ω(n).

I think I have a function like this, $$f(n) = (1 + \sin n) \cdot 2^{2^{n+2}}.$$ But I'm not entirely sure of how to prove this. If anyone can think of a better function, please go ahead I would ...
3
votes
1answer
91 views

How to find asymptotic of function s=s(n): s^s = n

How to find asymptotic of function s=s(n): $s^s = n$. Please help me to solve this problem.
0
votes
2answers
60 views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n) = \Theta(n^2) $ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2 $. I don't understand how to subtract off ...
6
votes
3answers
161 views

Is there a minimal diverging series?

Is there a function $f:\mathbb{N} \to \mathbb{R}^+$ s.t. its series $\Sigma_{i=0}^\infty f(n)$ diverges but the series for all function in $o(f)$ converge?
0
votes
2answers
55 views

Is there a diverging series in $o(1/n)$

Is there a function $f : \mathbb{N} \to \mathbb{R}^+$ in $o(1/n)$ s.t. $\Sigma_{i=0}^\infty f(n)$ diverges?
18
votes
2answers
427 views

Asymptotic analysis of the integral $\int_0^1 \exp\{n (t+\log t) + \sqrt{n} wt\}\,dt$

The integral I'm trying to study is $$ F(n) = \int_0^1 \exp\left\{n(t+\log t)+\sqrt{n}wt\right\}\,dt, \tag{1} $$ where $w$ is a fixed complex number with $\Re(w) < 0$ and $\Im(w) > 0$. As ...
2
votes
1answer
91 views

How are these two terms asymptotically equal?

My teacher claim these two are the same in a proof, but I'm not sure if this is correct. Could anyone shed me some lights? $$\log_2((\lceil \log_2{n} \rceil)!) = \log_2(n) \cdot \log_2(\lceil ...
1
vote
1answer
51 views

Estimation of recurrent sequence

Suppose we have $z_{n+1}=\frac{z_{n}^2}{1+cz_{n}}$ where $c>1$ and $z_{1}>0$. What can we say about $z_{n}$? Can we find an explicit formula? Can we at least get an approximation of the form ...
3
votes
2answers
978 views

Disproving big O

In the question, we are to assume that f(n) is O(g(n)). Next, we have to decide whether 2^f(n) is O(2^g(n)). According, to some solutions on the internet, this can be proven to be false if we take ...
0
votes
2answers
970 views

proof that a function plus a lower growth function is theta the first function.

my assignment is to (dis)prove the following f(n)+o(f(n))=Θ(f(n)) for example: for all n >= n', n + log(n) = c*n so ...
1
vote
0answers
46 views

Invert big-O involving logarithms while retaining a good error term

I have an equation $$ y=\frac{kx}{\log(y/k)-1}+O(1) $$ which I would like to solve for $y$ in terms of $x$ ($k$ is constant). Clearly $y\sim kx/\log x$ but I would like to preserve the error term. ...
0
votes
1answer
108 views

asymptotic sequence

I am asked to prove that $x^n(a+\cos(x^{-n})$ is an asymptotic sequence for $n=0,1,2,...$, $a>1$, $x\rightarrow 0$ but its derivative wrt x isn't an asymptotic sequence. ...
1
vote
1answer
272 views

Asymptotic growth comparison

When comparing the two functions: $2^{\sqrt{\log_2 n}}$ and $\sqrt{n}$ is it correct to say: \begin{align*} \lim_{n \to \infty} \frac{2^{\sqrt{\log_2 n}}}{\sqrt{n}} & = \lim_{n \to\infty} ...
0
votes
2answers
134 views

Asymptotic growth

I am given a list of functions and I am asked to order them in accordance with their asymptotic growth; Here I would just like to verify that my approach is valid. In the case of comparing: $\log ...
3
votes
2answers
207 views

asymptotic analysis: what is a basic approach to this?

I am just looking for basic step by step in how to turn a pseudo code algorithm into a function and then how to calculate and show T(n) ∈ O(f(n)), and that T(n)∈ Sigma(f(n)) Also if someone could ...
0
votes
1answer
142 views

Is there any “nice” function whose MacLaurin series has certain properties?

In learning about asymptotic expansions of functions, I've encountered several problems where a particular pattern of powers is coming into play, and I'm finding functions that I can readily show to ...
-1
votes
1answer
180 views

How to find asymptotic entire functions?

I want to know how to find analytic functions $f(z)$ that are asymptotic and analytic on and near the real line of functions of the type $\ln(C +\exp(P(z^2)))$ where $C$ is a complex constant and $P$ ...
2
votes
2answers
84 views

Asymptotics of $nT(1) + \frac{n}{\lg5}\sum_{i=1}^{\log_5 n}\frac{1}{i}$

I am trying to find asymptotics/running time of recurrence $T(n) = 5T(\frac{n}{5}) + \frac{n}{\lg n}$. Since Master Theorem for solving the reassurances can't be used, I was able to unroll it and came ...
0
votes
1answer
144 views

Upper bound of function including Pochhammer symbol

How can I find the upper bound of $$\left\vert\frac{(c+1/2+\lambda)_{n}}{\lambda^{n}}\right\vert,\quad\text{where}\quad(c+1/2+\lambda)_{n}=\frac{\Gamma(c+1/2+\lambda+n)}{\Gamma(c+1/2+\lambda)}$$ and ...
1
vote
1answer
106 views

Proving that $f(x)$ is not $O(\log f(x))$

I tried to prove (by contradiction) that, given a positive function $f(x)$, it is not $O(\log(f(x))$ (in this case, log denotes the base 2 logarithm). The problem is that I do not know anything about ...
3
votes
1answer
212 views

Asymptotic analysis Big O Big Omega

When we have $F(n) = \Omega(H(n))$ and $G(n)=\mathcal{O}(H(n))$. Can we prove that $G(n)/F(n) = \mathcal{O}(1)$? I tired to use the definitions of $\mathcal{O}$ and $\Omega$ but all I ended up with ...
1
vote
1answer
184 views

How to prove that a function f(n) exists/belongs to bigTheta?

So as per the title, I'm trying to prove that a function $f(n) = n^2 + 8n$ exists in $\Theta (n^2)$. What I'm having trouble with is the logic/concept behind doing so. By definition, it would mean ...
1
vote
2answers
3k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
3
votes
1answer
322 views

All asymptotes of $f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$

Find the number of all possible asymptotes of: $$f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$$ Since we know $\sqrt{ax^2+bx+c}\approxeq \sqrt{a}\big|x+\frac{b}{2a}\big|$ when $(x\rightarrow\pm\infty)$ so, ...
2
votes
1answer
81 views

What is the value of this summation in Big O terms?

I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below: $$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$ What will be the Big O ...
4
votes
1answer
179 views

If $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$?

This may be a dumb question, but if $f(n)\in O(g(n))$ can $g(n)\in O(f(n))$? I can think of a few counter examples, like $n\in O(n^2)$ and obviously $n^2\notin O(n)$, but one counter example doesn't ...
1
vote
1answer
91 views

Estimate cardinality of the set

Prove that: $$\left|\left\{ \langle a,b \rangle\in \mathbb{N}\times\mathbb{N}:a^2+b^2\le n \right\}\right|=\frac{\pi}{4}n+O(\sqrt{n})$$ I heard something about that the number of lattice points ...
5
votes
1answer
72 views

Estimate sum with a very small error

Estimate sum: $$\sum_{i=1}^{n}\frac{i}{n^2+i}$$ with an absolute error $O\left(\frac{1}{n^2}\right)$ So far, estimation with integrals was sufficient for me, but here the error has to be very ...
1
vote
1answer
124 views

convergence of an oscillatory integral

Let $\alpha$ be real numbers and let $f\colon\mathbb{R}\to \mathbb{C}$ be a function in $L^2 (\mathbb{R})$ (actually smooth and compactly supported, but this doesn't seem to be relevant). I am ...
3
votes
2answers
73 views

Asymptotic analysis of a recurring sequence

Let $(u_n)$ be a sequence defined by: $$\begin{equation} \left\{ u_0 \geq 0 \\ \forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}} \right. \end{equation}$$ I'd like to prove that when $n ...
2
votes
2answers
303 views

A systematic way to estimate the cardinality of a set

Let me take the following set as an example: \[ A = \lbrace \langle a,b \rangle \in \mathbb{N} \times \mathbb{N} : a^2 + b^2 \leq n \rbrace . \] One approach would be to notice that $A$ is the set ...
3
votes
3answers
194 views

A couple of asymptotics exercises

Recently I've been following the chapter on asymptotics in Concrete Mathematics. The subject matter of it is relatively new to me though and I'm having some difficulties dealing with asymptotic ...
0
votes
0answers
41 views

Estimating the recurrence $T(n,i) = (\lfloor\frac{n-i}{i}\rfloor \cdot i ) + T(i + (n \operatorname{rem} i), (n \operatorname{rem} i))$

Given $i < n/2$ and denoting $[x]$ to be an integer part of $x$ (floor$(x)$) and $(a \operatorname{rem} b)$ to be a reminder when $a$ is divided by $b$. $$ T(n,i) = ...
0
votes
3answers
254 views

Maple Error on Asymptotic Analysis of $\ln(n)!$

In Maple, the command asmypt($f$,$x$) computes the asymptotic expansion of the function $f$ with respect to the variable $x$ (as $x \rightarrow \infty$). The command asympt(ln(n)!,n); gives the ...
0
votes
0answers
58 views

Estimating cardinality of a set

Estimate |$\{<a,b,c> \in \mathbb{N}:a^2+b^2+c^3 \le n\}$| with absolute error of $O(n)$.