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

Why does my induction proof of an algorithm's running time always seems tautological?

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. ...
1
vote
1answer
21 views

Computing the limit of $(\lg n)^{0.5}/\lg(n^{0.5})$

$$\lim_{n\to\infty}\frac{(\lg(n))^{0.5}}{\lg(n^{0.5})}$$ I'm really not sure where to begin with this. Are there some basic laws of logs that I should apply first?
1
vote
1answer
38 views

Understanding Little Oh Notation Proof - Prove the function$ f(n) = 12n^2 + 6n\ \ is\ \ o(n^3)$

Here is the problem and proof given by my book: Prove the function $f(n) = 12n^{2}+6n$ is o($n^{3}$) Let us first show that $f(n)$ is o($n^{3}$) Let $c \gt 0$ be any constant. If we take ...
0
votes
0answers
20 views

Is not true that $2^n \notin \Theta(2^{n/2})$? [on hold]

I have recently seen it claimed in a book that $$ 2^n \notin \Theta(2^{n/2}) $$ Yet this seems wrong to me since $$ 2^{n/2} = {2^n \over 2} = \Theta(2^n) $$ Am I missing something?
1
vote
0answers
20 views

If $\lg(n!) = \Theta(n \lg n)$, does $\lg(n!) = \Theta(\lg(n^{n^n}))$ as well?

First consider that we have: $$ \begin{align} \lg(n!) &= \overbrace{\lg\Bigg(\sqrt{2\pi{n}}\Big(\frac{n}{e}\Big)^n\Big(1+\Theta(\frac{1}{n})\Big)\Bigg)}^{\text{Stirling's Equality}} = ...
1
vote
4answers
32 views

Asymptotic behaviour of the logarithm

In this post, the poster suspected that the $\log$ function would eventually flatten out and approach a straight line. We all know this isn't true of course. But then a commenter pointed out this: ...
1
vote
1answer
35 views

Evaluate the integral $\int_0^{\infty} e^{\frac{-t(s-1)^2}{2}} \left( \frac{t(s-1)^3}{3} \right) ds$

I am attempting to evaluate the integral (where $t \rightarrow \infty$) $$I(t) = \int_0^{\infty} e^{\frac{-t(s-1)^2}{2}} \left( \frac{t(s-1)^3}{3} \right) ds$$ which occurs in the calculation of the ...
0
votes
1answer
10 views

Which Function is Big-O of the Other

Given $f(n)=nlog(n)$ and $g(n)=10^{-6}n^2$, I am asked to find whether $f\in O(g)$ or $g \in O(f)$. The book claims that $f \in O(g)$, but I do not see how that is true. If it is true, there exists ...
2
votes
0answers
25 views

Find the angle between asymptotes

Sketch the locus of the centres of circles which touch two fixed and unequal circles. Find the angle between the asymptotes How shall I find the locus when the size of the circles are not ...
2
votes
2answers
38 views

How to find Big O notation here.

How can I express the formula (logn + 2)*(n - 1) using big-O notation My try:- (logn + 2)*(n - 1) => nlogn + 2n - logn - 2. Now I am confused whether this is O(n) or O(log n)
2
votes
1answer
24 views

Determining a succinct big $\Theta$ expression [on hold]

Determine a succinct big-$\Theta$ expression for the growth of function $$ (\log^{50}n)n^2 + n^{2.1}(\log n^4) + 1000n^2 + 100000000n $$
0
votes
1answer
18 views

Proving the asymptotic relationship between $(lg\cdot n)^{0.5}$ and $lg\cdot (n^{0.5})$?

Say $f(n) = (lg\cdot n)^{0.5}$ and $g(n) = lg\cdot (n^{0.5})$ It would appear that $f(n) = O(g(n))$ for $n \gt 55$ correct? How do I go about proving the the relationship for this?
0
votes
0answers
18 views

Asymptotic notations (Big Omega) [on hold]

Use the definition of big- $\Omega$ to prove that $n + n(\log n)^2 = \Omega(5n + 9n(\log n)^5)$. Provide the appropriate $c$ and $k$ constants ? I am new to the topic : Advanced Analysis of ...
-2
votes
1answer
35 views

Show $n + n^2 \mathcal O(\ln (n))= \mathcal O(n^2 \ln (n))$ [on hold]

Show that $$n + n^2 \mathcal O(\ln (n))= \mathcal O(n^2 \ln (n))$$
0
votes
2answers
80 views

prerequisit for BigO notation

I have been trying to learn algorithms for a long time now and I am really struggling with the math part and don't know what to do. I only know very basic math, so my question is what do I have to ...
1
vote
0answers
18 views

A Question from Murray - Asymptotic Analysis

I'm stuck on one of the questions related to the method of stationary phase in Murray's book on Asymptotic analysis. The question is as follows; If $h(t)$ has a single stationary point at $t_0$, ...
0
votes
0answers
19 views

Big $O$ question for While and For loops [on hold]

I have to find the exact $O(N)$ for these instructions, not just the order of magnitude. I'm not getting any of the answers provided for me. I know the first loop is $O(3N+2)$. The declaration of ...
-1
votes
2answers
21 views

Arrange the following growth rates in increasing order O((35)^n),O(n^4),O(1),O(n^3 logn) [duplicate]

I want to Arrange the following growth rates in increasing order This order are following : O((35)^n),O(n^4),O(1),O(n^3 logn) Please give me idea how to arrange growth rates in increasing order
0
votes
0answers
32 views

Understanding $\Theta$-notation rigorously

Let $f$ and $g$ be functions on $\mathbb{N}$. If $f(n) \in \Theta(g(n))$, we say that (for sufficiently large input) "the function $f(n)$ is equal to $g(n)$ to within a constant factor". What does ...
2
votes
0answers
42 views
+50

Name for kind of big O notation with leading coefficient

Context: As known the big O notation $O(f(n))$ describes a function $g(n)$ such that there is a constant $C \ge 0$ with $\limsup_{n\to\infty} \left|\frac{g(n)}{f(n)}\right| \le C$ (I assume that ...
-1
votes
1answer
27 views

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ [on hold]

Show that $f(n)$ is $O(g(n))$ then $f(n)+c$ is $O(g(n))$ for all constants $c$. In our class, $$O(g(n)) = \{f(n) \mid \exists C,n_0 \colon \forall n \geq n_0 \colon |f(n)| \le C|g(n)| \}$$
1
vote
3answers
36 views

$O( n^3)$ vs $O(n^2 \ log n)$

I was wondering how $n^3$ compares to $2n^2 \log n$ as I thought that $n^3$ is $\Omega(n^2 \log n)$ but there is the fact that $n$ is $O(n \log n)$ so I wasn't sure whether it is bigO or $\Omega$
0
votes
1answer
34 views

What is the big Oh notation for the following series.

I have the series $1+3+9+27+... + 3^n$ . I need to find the Big O solution. What I have tried. The above series is a Geometric Progression with r=3. SO the sum would be. $ [1* 3^{n+1} - 1]/2 $ How ...
1
vote
0answers
18 views

asymptotic of an interesting recurrence realtion (more general case)

A link to the original question for reference:Click here I tried to study a more general situation: Let $y_{d,d}=1$ and $$ ...
0
votes
1answer
51 views

Simplifying $f(x) = \left(x^{3} + 2x^{2} + O(x)\right)\cdot\left(1 + \frac{1}{x} + O\left(\frac{1}{x^{2}}\right)\right) $

Simplify $$f(x) = \Big(x^{3} + 2x^{2} + O(x)\Big)⋅\Bigg(1 + \frac{1}{x} + O\bigg(\frac{1}{x^{2}}\bigg)\Bigg) $$ as $x \to +\infty$. I am a bit stuck as to what to do with the three sets of ...
0
votes
0answers
17 views

Comparing functions

I wanted to make sure I had the correct understanding of the following big $O/\Theta/\Omega$ questions and I figured it would be better posted here than SO as it was more about comparing function. a) ...
0
votes
0answers
21 views

“Asymptotic” $\mathbb{R}$-algebras

Definition. By an asymptotic $\mathbb{R}$-algebra, I mean an $\mathbb{R}$-algebra $F$ of functions $\mathbb{R} \rightarrow \mathbb{R}$ satisfying: $$\mathop{\forall}_{f:F}\left[\left(\lim_{x ...
0
votes
0answers
20 views

What do we call the number that measures how good of an asymptote $g$ is to $f$, and what are the basic results about this number?

Suppose we have a (potentially very complicated) smooth function $f : \mathbb{R} \rightarrow \mathbb{R},$ and we're trying to approximate it (in the limit as the input value goes to $+\infty$) by a ...
1
vote
1answer
18 views

Large pairwise coprime sets

Say that a set $S\subseteq\Bbb N$ is pairwise coprime if every two elements of $S$ are relatively prime. Denote by $f(n)$ the size of a maximal pairwise coprime subset of $\{1,...,n\}$. What is ...
1
vote
1answer
24 views

Product property of Big O

Trying to prove: If $f(n)$ and $g(n)$ are both $O(h(n))$, then $f(n)*g(n)$ is $O(h^2(n))$. Understanding so far : The product of upper bounds of functions gives an upper bound for the product of ...
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
0
votes
1answer
19 views

Asymptotic error expansion of global error for single step methods

My question refers to the proof of the following theorem, but it may suffice to just skip the theorem and continue with the problematic taylor expansion $(\ast)$: Let $f(t,y)$ and the single step ...
0
votes
2answers
47 views

How to show that $O(n^\frac{3}{4} \log n) = O(n)$?

I try to analyze LazySelect algorithm (finds kth order statistic of a set). One of the steps is to take a sample of $n^\frac{3}{4}$ elements and sort it. It seems like this sorting is linear relative ...
2
votes
0answers
61 views

Arithmetic progression of squarefree integers?

Let $x$ be a given positive integer. I'm intrested in the longest arithmetic progression of squarefree integers within the interval $(x,x^2)$. Both constructive and nonconstructive results. For ...
1
vote
2answers
59 views

Why is $\binom{2n}{n} \asymp \Theta \big(\frac{2^{2n}}{\sqrt{n}}\big)$?

I saw this statement : $$\binom{2n}{n} \asymp \Theta \bigg(\frac{2^{2n}}{\sqrt{n}}\bigg) \asymp \Theta\bigg(\frac{4^n}{\sqrt{n}}\bigg)$$ How did we go from the first statement to the second? I tried ...
2
votes
1answer
40 views

Estimate integral $\,\displaystyle\int_{0}^{\infty}\operatorname{sech}\left(\varepsilon x\right)\cos\left(kx\right)\,dx,\,$ with $\,k,\varepsilon>0$

$ \newcommand{\sech}{\operatorname{sech}} $ Is there any analytic/asymptotic way to estimate the value of the integral: $$ \int_{0}^{\infty} \sech\left(\varepsilon x\right)\cdot ...
1
vote
0answers
15 views

what happens when expansion parameter is of the order of dynamical variable itself?

Lets consider following differential equation, $\epsilon \frac{dy}{dt} = ....$ In principle one can use Method of matched asymptotic expansion or Method of multiple scales to solve such singular ...
1
vote
3answers
74 views

Missing steps: Show the sum of the first n positive integers is of order $n^2$

In Rowsen's Discrete Mathematics text, 6th edition. He has this problem as an example (#11) on page 190. His solution for obtaining a lower bound is to ignore the first half of the terms. He does the ...
3
votes
1answer
64 views

Does writing $f(x)\sim \ell$ have a sense?

If $\lim_{x\to a}f(x)=\ell$, is it correct to say that $f(x)\sim_a \ell$ ? I would say yes since $\lim_{x\to a}\frac{f(x)}{f(a)}=1$, but on a test I wrote $e^{-t}\sim_0 1$ and the corrector said that ...
2
votes
2answers
29 views

Asymptotic of $ \sum_{r=1}^{k} \frac1{r^{3/2}}$ - Generalized Harmonic Number

What is the asymptotic approximation of the following generalized Harmonic number as $k \to \infty$ ? $$H(1.5,k) = \sum_{r=1}^{r=k} \frac{1}{r^{1.5}}$$ (there is a similar question posted on ...
-2
votes
2answers
31 views

specifying an asymptotic function

Please help me out; I need to specify a function satisfying these conditions: $$ f(0)=1 \;\;;\;\lim_{x \to \infty}f(x)=0$$ Hopefully does there exist a simple answer? Thanks a lot!
2
votes
0answers
50 views

Approximate an integral with Bessel functions

Given $r,a,\lambda\in\mathbb{R}$, $r<a$, how can I find an approximate solution for the following definite integral? $$ \int_0^\infty J_0 (\lambda r)J_1(\lambda a)\frac{1}{\sqrt{n+\lambda^2 ...
1
vote
2answers
34 views

oblique asymptote problem

I can't resolve limit for oblique asymptote for: $$\frac{2x^2 e^{1/x}}{2x+1}-x$$ I've tried solving it by putting the common denominator but it's a bit confusing because the numerator is bigger then ...
0
votes
0answers
23 views

Simple question about asymptotic notation

I'm quiet new to the asymptotic world, so apology in advance if this question seems too trivial for you experts. Given $\frac{2kn2^{-k}}{E[X]}.$ As $k \sim 2\text{log}_{2} n$, the numerator is ...
0
votes
0answers
41 views

For any arithmetic progression $n \in \Bbb{N} : n \equiv b \pmod a$, the natural density is $\frac{1}{a}$?

This question comes from here (page 10). Given that $d(A) := \lim_{x\to\infty}\frac{1}{x}\sharp\{n \leq x : n \in A\}$, how do I get that: 1) $d(n \equiv b \pmod a) = \lim_{x\to\infty}(\left [ ...
0
votes
0answers
29 views

How to prove $x^m = O(e^x)$ for any $m \gt 0$?

My attempt: It's true for $m = 1$ clearly. Now assume true for $m=1\dots M-1$. Then $x = O(e^x)$ and $x^{M-1} = O(e^{M-1})$. Lemma: if $f = O(g)$ and $f' = O(g')$ then $ff' = O(gg')$. Proof: $f = ...
1
vote
2answers
31 views

Simple question, what is meant by 'as $x \to \infty$ the number of squares $\leq x$ is $\sqrt{x} + O(1)$?

For $x \to \infty$: the number of squares $n^2 \leq x$ is $\sqrt{x} + O(1)$. From here (page 6). More specifically, do they mean that... I'm confused now. I'm really not sure what they mean ...
3
votes
1answer
62 views

Calulate a limit involving $\zeta{(\zeta{(z)})}$

I'm currently trying to evaluate the following limit: $$ \lambda=\lim_{z\to\infty}{\left[2^z-\left(\frac{4}{3}\right)^z-\zeta{(\zeta{(z)})}\right]} $$ A look at numerical approximations suggests, that ...
-2
votes
0answers
50 views

BIG OH:$ f (x) = 3x^3 + 2x + 4$. One has

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
3
votes
1answer
33 views

$\sum_{n \leq x} \frac{1}{n} = \int_{1}^x \frac{dt}{t} + O(1)$ help deriving it

On page 5 of: Probabilistic Number Theory by Dr.J¨orn Steuding, there's $\sum_{n=2}^{[x]} \frac{1}{n} \lt \int_{1}^{[x]} \frac{dt}{t} \lt \sum_{n=1}^{[x] - 1}$ Therefore integration yields: ...