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

learn more… | top users | synonyms (1)

2
votes
0answers
32 views

Asymptotic Approximation

After analyzing performance of a cooperative system, I get the following expression for the system outage probability: $P = 1 - \frac{{{e^{ - 2\mu /{\beta _M}}}}}{{\Gamma \left( {{\alpha _3}} ...
1
vote
0answers
40 views

On n! divided by a product of primes and related questions

We have the following Definition 1. For integers $n\geq 1$ we define $$f(n) = \begin{cases} 1, & \text{if $n=1$} \\[2ex] \frac{n!}{\prod_{p\leq n}p}, & \text{if $n>1$} ...
0
votes
0answers
37 views

Distribution of the test statistic?

Let $\mathbf{x}_i \sim \mathcal{N}(\boldsymbol\mu, \boldsymbol\Sigma)$. I am trying to find a distribution of the following test statistic $ T(\mathbf{x}) = \frac{\bar{\mathbf{x}}^T ...
1
vote
1answer
29 views

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

$$\lim\limits_{n\to\infty}\frac{(\log n)^{0.5}}{\log 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?
0
votes
1answer
22 views

Rigorously prove while loop executes $\lceil \log_{2}(\log_{2}(n)) \rceil$ times

Problem Suppose we have the following code k := 2 while k < n do k := k * k end while How many times will the loop execute? Current Work My intuitive ...
1
vote
1answer
36 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
43 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
35 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 ...
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 ...
21
votes
2answers
1k views

A (non-artificial) example of a ring without maximal ideals

As a brief overview of the below, I am asking for: An example of a ring with no maximal ideals that is not a zero ring. A proof (or counterexample) that $R:=C_0(\mathbb{R})/C_c(\mathbb{R})$ is a ...
2
votes
2answers
56 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
0answers
28 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
3answers
83 views

Show that $\frac{1}{2}n^2-3n=\Theta{(n^2)}$

Show that $$\frac{1}{2}n^2-3n=\Theta{(n^2)}$$ $$$$ $\displaystyle{\frac{1}{2}n^2-3n=\Theta{(n^2)}: \\ \exists c_1, c_2 >0 , \ \ \exists n_0 \geq 1 \text{ such that } \forall n \geq n_0 \\ ...
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
0answers
19 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 ...
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?
2
votes
0answers
46 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 ...
-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))$$
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
21 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
vote
3answers
112 views

how to prove $\sum_{i=1}^n i^k =\Theta(n^{k+1})$

we can say that if all $i$ s in the sum were equal to $n$ then the answer to the summation would be $n\cdot n^k$. So $n^{k+1}$ is the upper bound.so $\displaystyle\sum_{i=1}^n i^k=O(n^{k+1})$ For ...
-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 ...
-1
votes
1answer
27 views

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

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
35 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
20 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 ...
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
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 ...
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 ...
18
votes
7answers
4k views

Stirling's formula: proof?

Suppose we want to show that $$ n! \sim \sqrt{2 \pi} n^{n+(1/2)}e^{-n}$$ Instead we could show that $$\lim_{n \to \infty} \frac{n!}{n^{n+(1/2)}e^{-n}} = C$$ where $C$ is a constant. Maybe $C = ...
7
votes
0answers
105 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
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
1answer
30 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
3answers
103 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
6
votes
1answer
174 views

The asymptotic of the number of integers that are sums of three nonnegative cubes

Let $c(n) $ be the number of distinct integers between $0 $ and $n $ of the form $ a^3 + b^3 + c^3$, meaning the sum of $3$ nonnegative cubes. $C(n) = O( n \space \ln(n)^x ) $ Find and prove the ...
2
votes
0answers
62 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
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 ...
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 ...