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

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
0
votes
3answers
63 views

Why $x=\pm1$ is not an asymptote of $\frac{x^3}{x^2+1}$?

By long division, $f\left(x\right)=\frac{x^3}{x^2+1}$is equal to $x-\frac{x}{x^2+1}$. Therefore, there is an asymptote $y=x$. But why there is no an asymptote $x=\pm1$? How to determine whether the ...
16
votes
4answers
638 views

Decreasing integers on the blackboard

There are $n\geq 2$ copies of an integer $k>0$ written on the blackboard. A move consists of choosing an integer $m>0$ on the blackboard, and replacing it as well as one other integer on the ...
1
vote
0answers
30 views

Find the order of the following expression as x->0

Could someone help me find the order of the following expression without using the quotient rule? $\frac{1-\cos(x)}{1+\cos(x)}$ I expanded the denominator and the numerator but not sure how I get to ...
3
votes
2answers
175 views

Find the asymptotic tight bound for $T(n) = 4T(n/2) + n^{2}\log n$

Find the asymptotic tight bound in $$ T(n) = 4T\left(\frac{n}{2}\right) + n^{2}\log n. $$ where $ \log n= \log _{2}n $ and $T(1) = 1$. I should solve this using all three common methods: iteration, ...
1
vote
0answers
42 views

Asymptotically evaluating integrals with oscillatory behaviour in both numerator and denominator

I have come across an integral that I would like to asymptotically evaluate (to leading order at least) which I have seen no mention of in standard textbooks. I want to evaluate an integral of the ...
1
vote
1answer
103 views

big O notation - explain the equality

$$\sum\limits_{i = 1}^{\log n} {\sqrt {{2^i}} } = O(n) $$ OK, So I understand the equality, but I don't know how to prove it. For my understanding, I need to show that the left side is $\le$ the ...
1
vote
0answers
68 views

How to prove that there are $O(T\ln T)$ zeros in the critical strip of the Riemann zeta function?

Define $F(T)$ as the number of solutions to $\zeta(a+ ti) =0$ for $0\le t\le T$ and $0<a<1$. How to show that $F(T)= O(T\ln T)$? For clarity, $\zeta$ is the Riemann zeta function, $i$ is the ...
6
votes
1answer
249 views

Asymptotic expansion for harmonic sum in two variables

I am interested in determining an asymptotic formula for the double summation of $1/(ab)$, where $a$ is an odd integer ranging between 1 and $k/\sqrt{j}$, $b$ is an odd integer ranging between $a$ and ...
0
votes
1answer
50 views

Big - Oh proof $n^{2^n} = O(2^{2^n})$

But the book asks me to prove that it's correct: $$n^{2^n} + 6*2^n = O(2^{2^n})$$ But I think, it's an incorrect one. Because, it's correct only for $n < 2$.
4
votes
3answers
259 views

Asymptotic expansion of $J(t) = \int^{\infty}_{0}{\exp(-t(x + 4/(x+1)))}\, dx$

I want to derive an asymptotic expansion for the following Bessel function. I think I need to rewrite it in another form, from which I can integrate it by parts. I am interested in obtaining the ...
1
vote
2answers
38 views

Growth rate of $1/(\log(x)-\log(x-1))$

Let $x>1$ be a real number. Let $y=\dfrac{1}{\log(x)-\log(x-1)}$. My question: Approximately how fast does $y$ grow (asymptotically) in terms of $x$? (e.g. linear, polynomial, exponential)?
0
votes
3answers
168 views

Prove that a circle has an infinite number of tangents

It seems obvious that a circle is comprised of the set of all points that are equidistant from one point, and that each point on the circumference of the circle represents a tangent. This seems to ...
8
votes
3answers
116 views

Sum $S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$

Consider the sum $$S(n,c) = \sum_{i=1}^{n-1}\dfrac{i}{ci+(n-i)}$$ where $0\le c\le 1$. When $c=0$, $S(n,c)$ grows asymptotically as $n\log n$. When $c=1$, $S(n,c)$ grows asymptotically as $n$. ...
4
votes
0answers
189 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
0
votes
1answer
140 views

Big $O$ and Big $\Theta$ proof

Use definitions to prove: If f and g are nonnegative, and f(n)=$\Theta$(h(n)) and g(n)=$O$(h(n)), then f(n)+g(n)=$\Theta$(h(n)) I know that f(n)=$\Theta$(h(n)) means that c|h(n)| <= |f(n) | ...
2
votes
1answer
42 views

Asymptotic behaviour of the area of a 2-dimensional flat subset of $\mathbb{R}^3$

I am interested by the area of the $2$-dimensional flat subset of $\mathbb{R}^3$ defined by the following equations with one parameter $t>1$: $x,y,z>0$ (positive octant) $x+y+z=t$ (hyperplane ...
0
votes
1answer
40 views

Determine convergence or divergence of a slowly increasing sequence

We have by the integral test: $\sum_{n=2}^{\infty}\frac{1}{n}=\infty$ $\sum_{n=2}^{\infty}\frac{1}{n\ln n }=\infty$ $\sum_{n=2}^{\infty}\frac{1}{n\ln n (\ln\ln n) }=\infty$ ...
6
votes
1answer
97 views

Limits of $\sum_{m=1}^{+\infty} \sum_{n=1}^{+\infty}e^{-mn x}$ at $0$ and $\infty$

Let $f(x) = \sum_{m=1}^{+\infty} \sum_{n=1}^{+\infty}e^{-mn x}$ for $x > 0$. Prove that $f(x) \sim e^{-x}$ as $x \to \infty$ and $\lim_{x\to 0} x\cdot (f(x) + \frac{1}{x}\log x)= \gamma$ where ...
0
votes
1answer
996 views

Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
1
vote
1answer
120 views

Find “singular expansion” of a function

I have the function $(1-z)^{-z}$, analytic except on $\mathbb{R}_{\geq 1}$ Now in the text, it says the "singular expansion" at $z=1$ is $\displaystyle \frac{1}{1-z} + \log(1-z)+O((1-z)^{1/2})$ I'm ...
0
votes
1answer
55 views

Differential equation how to find out bounded or not bounded

For which value of the parameter $k$ will all solutions of remain bounded as $t \rightarrow \infty$? $$u''(t)+k~u(t)=2 \sin(10t)?$$
0
votes
0answers
36 views

Proving the sum of two functions is $\Theta$ of the max of those functions? [duplicate]

Suppose that the functions $\ f_1, f_2, g_1, g_2: \mathbb{N}\to\mathbb{R}$ (set of real numbers greater or equal to 0) are such that $\ f_1 \in \Theta \ (g_1)$ and $\ f_2 \in \Theta \ (g_2)$. Prove ...
1
vote
1answer
64 views

Suppose $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2)$. Prove $(f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$.

I need to prove that $f_1 \in \Theta(g_1) \land f_2 \in \Theta(g_2) \implies (f_1 + f_2) \in \Theta(\max\{g_1, g_2\})$ This question is relevant, but I have a slightly different case, so I don't ...
4
votes
1answer
102 views

Finding a tight upperbound

A call graph $G = \{V,E\}$ on phone metadata has a vertex $v \in V$ for each phone number and an edge $\{v,w\} \in E$ if there has been a phone call between $v$ and $w$. One can monitor calls of a set ...
0
votes
1answer
190 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
1
vote
0answers
37 views

How to find the influence function of $\int_{[0,t]}(1-F_\_)^{-1}dF$,i.e., cumulative hazard function

The common strategy is to replace $F$ with $(1-t)F+t\delta_x$ and then expand the integral. However, I am not sure how to deal with $F_\_$. It seems different from $F$.
-1
votes
1answer
398 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
3
votes
1answer
151 views

Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?

Stirling's approximation of the factorial for even numbers is given by $$ (2n)! \sim \left(\frac{2n}{e}\right)^{2n}\sqrt{4 \pi n}. \tag{1} $$ Further, the Euler numbers grow quite rapidly for large ...
0
votes
2answers
66 views

If $f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or any other one-line relation?

$f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or $$\lim_{x \to \infty}[f(x)/g(x)]=1$$ where f(x)=pi(x)(prime counting function) and g(x)=li(x)(logarithmic ...
1
vote
0answers
22 views

parametric integral and asymptotic representation

Here is a parametrial integral $$I(a)=\int_0^{\pi}\int_0^{\pi} ...
10
votes
2answers
353 views

Integral $S_\ell(r) = \int_0^{\pi}\int_{\phi}^{\pi}\frac{(1+ r \cos \psi)^{\ell+1}}{(1+ r \cos \phi)^\ell} \rm d\psi \ \rm d\phi $

Is there a closed form for $|r|<1$ and $\ell>0$ integer? The solution for the special cases $\ell=2$ and $4$ would also be interesting if the general case is not available. Integrating ...
0
votes
1answer
83 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
1answer
79 views

How to define theta in terms of omega and O?

I am trying to prove some logical stuff using the definitions of BIG O, BIG Theta and BIG Omega. Unfortunately I am a bit confused. And how can we represent Θ in terms of of those other notations? ...
1
vote
1answer
40 views

Is $O(n \log n)$ always smaller than $O (m)$ for $n-1 < m < n^2$?

I am writing an algorithm that needs to finish in $O(m)$. The problem is for a graph $G( V, E )$, where $m = |E|$ and $n = |V|$. $m$ can be in the range of $n-1$ to $n^2 - 1$. If I do some ...
0
votes
2answers
48 views

Algorithm Analysis on Recurrence Relation.

Consider the following recurrenc relation: $f(n) = f(n/2) +nlogn$ Since this does not honor the form of the Master Recurrence, we need to obtain an estimate of the asymptotic order of $f$. According ...
0
votes
2answers
35 views

Prove $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$

Prove that $10^3n^4+10^{-3}2^n=\mathcal O(2^n)$ I started this proof by trying to use induction, although as I put in $n=1$, although this gives: (when $n=1$) $1000.0002<2$ This is clearly untrue ...
2
votes
1answer
112 views

Asymptotic Expansion of a nearly divergent integral

I want to understand the asymptotic behavior of an integral of the form $$ I_f(\epsilon) = \int_0^1 \frac{\log(1/x)}{\sqrt{x}\sqrt{x+\epsilon}} f(x) dx $$ as $\epsilon \to 0^+$ for a generic function ...
2
votes
2answers
143 views

Proving a BIG-O statement? Logarithmic expressions. Simple Induction.

I have to write a proof for the following statement. $$\log_2(n!)\in\mathcal O(n\log_2(n))$$ What approach would you recommend. I am kind of LOST trying to figure this out. I transformed the ...
1
vote
0answers
78 views

Integration by parts in vector calculus

I have an axi-symmetric integral (the domain and all functions are axi-symmetric) in cylindrical coordinates which needs to be integrated by parts for use in a finite element code. The integral is ...
1
vote
0answers
51 views

How to prove that $\sum_{p \leq x} {\log p \over p} = \log x + O(1)$? [duplicate]

Problem Prove that $$ \sum_{p \leq x} {\log p \over p} = \log x + O(1) $$ as $x \to \infty$. Notes: $p$ ranges over primes, $\log$ is natural Progress Using Riemann-Stieltjes integration and ...
5
votes
1answer
198 views

How to prove this inequality $\pi(x) > \log x - 1$ involving the prime counting function?

Problem Prove that $\pi(x) > \log x - 1$. Progress Based on a hint and very elementary methods, I got that $$ \prod_{p \leq x} (1-p^{-1})^{-1} \leq \prod_{k=2}^{\pi(x)+1} (1-k^{-1})^{-1}. $$ The ...
13
votes
5answers
1k views

Is there any nonconstant function that grows (at infinity) slower than all iterations of the (natural) logarithm?

Is there any nonconstant function that grows at infinity slower than all iterations of the (natural) logarithm?
0
votes
1answer
51 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
13
votes
1answer
166 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
1
vote
1answer
27 views

Big O notation question of Kolman's book

If $$f(x) = x^{100} , g(x) = 2^x. $$ Show that $f(x)$ is a big $O(g(x))$, but $g(x)$ is not big $O(f(x))$.
1
vote
2answers
128 views

Asymptotics of logarithms of functions

If I know that $\lim\limits_{x\to \infty} \dfrac{f(x)}{g(x)}=1$, does it follow that $\lim\limits_{x\to\infty} \dfrac{\log f(x)}{\log g(x)}=1$ as well? I see that this definitely doesn't hold for ...
0
votes
1answer
47 views

Does $ \log(x)^{x^a}$ eventually dominate $x^k$?

Does $ \log(x)^{x^a}$ eventually dominate $x^k$ for all $a\gt 0$ and for all positive integers $k$? And if so, how does one prove this? Thanks a lot for your help.
8
votes
3answers
338 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
1
vote
3answers
62 views

Show $f(x) = (x^4+x^2+1)/(x^3+1) $ is $O(x)$

How would I find the witnesses $C$ and $k$ such that $f(x)$ is $O(x)$? What I tried was $$(x^4+x^2+1)/(x^3+1) ≤ (x^4+x^4+x^4)/(x^3+x^3) = (3/2)x $$ for values $x>1$. $C = 3/2, k = 1$ Is this ...