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

learn more… | top users | synonyms (1)

-1
votes
1answer
36 views

Why is this big oh $O(n^3)$

Why is this big oh $O(n^3)$? (b) Give a good big-Oh bound on the function $$f(n)=2^{\log_2 n} n^2 + 3n^2 \log_2 n +n -17$$ I am not sure on how to solve this. If someone could help me solve, I ...
0
votes
4answers
63 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
3
votes
1answer
29 views

Prove $O(f(n)+g(n)) = O(f(n))$ when $g(n)=O(f(n))$

Given $g(n) = O(f (n))$, how can I prove that the following expression is true: $O(f (n) + g(n)) = O(f (n)) \tag1$ So I just write down what it says: $g(n) = O(f (n)) <=> f(n) \le c_1 g(n)...
2
votes
2answers
20 views

Asymptotic upperbound in multiplication

How can someone calculate the asymptotic upperbound of $2^nn^2$? The first term ($2^n$) grows much faster than the second, but saying that as a final result $2^nn^2 = O(2^n)$ would only be true in the ...
1
vote
1answer
37 views

What is the asymptotic behavior of this integral?

The function $F(x)$ is defined by the following integral $$F(x)=\int_0^x\frac{\left(1-y^3\right)^a}{\sqrt{\left(\dfrac{1-y^3}{1-x^3}\right)^b-\left(\dfrac{y}{x}\right)^4}}\,dy$$ where $a$ and $b$ ...
2
votes
0answers
17 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
0answers
30 views

Finding the inverse of a function involving logarithms

Let $A \asymp B$ mean that there exists universal constants $m,M >0$ such that $mA \leq B \leq MA$. Let $k,n \in \mathbb{N}$ be such that $\log n \leq k \leq n$. I want to prove that $$ k \log(\...
0
votes
0answers
35 views

Find the best Big-O estimate

Find the best (i.e., lowest) big-O estimate for the following function: $f(n) = 1 + 3 + 5 + 7 + ...+ (2n-1)$ Since the sum would be $f(n)= \frac{1 + n(2n-1)}2$, that would leave $\frac {2n^2 -n +...
1
vote
1answer
69 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
0
votes
3answers
53 views

Is $n^\frac{1}{10} \in O((\log n)^{10})$?

This question came up in a recent discussion: is $n^\frac{1}{10} \in O((\log n)^{10})$? First time I've come across a power of a log in a long time, and as far as I recall, there are no identities ...
0
votes
1answer
25 views

Big O Notation asymptotic relationship

I cannot prove correctness/incorrectness of the implication of two functions f(n) and g(n) in Big-Oh/asymptotic notation $$g(n) = \Omega(f(n)) ) \implies g(n) = O(n^2f(n))$$ I believe $g(n) = \Omega(...
1
vote
0answers
42 views

Can you get the average order of $ \left( 1+|\mu(n)| \right)^{M(n)} $, where $\mu(n)$ and $M(n)$ are the Möbius and Mertens functions, respectively

When yesterday I was interested in do a little study about the arithmetic function $$f(n)=\left( 1+|\mu(n)| \right)^{M(n)},$$ defined for integers $n\geq 1$, which $\mu(n)$ is the Möbius function and $...
0
votes
0answers
13 views

Renormalization Group

I am studying singular perturbation technique right now. Can anyone suggest introductory books on singular perturbation using renormalization group method? I have several books on perturbation theory ...
1
vote
1answer
39 views

Why does $\frac{\frac12 x+\frac18x^2+O(x^3)}{\frac12x-\frac18x^2+O(x^3)}=1+\frac12x+O(x^2)$?

I was reading the solution to a limit through Taylor expansion but did not understand this passage: $$g(x)=\frac{1-\sqrt{1-x}}{\sqrt{1+x}-1}=\frac{\frac12 x+\frac18x^2+O(x^3)}{\frac12x-\frac18x^2+O(...
1
vote
4answers
56 views

How to check if $n!$ is $ O(2^n)$

How can I check if $n! \in O(2^n)$? The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$. What is the clearest way to solve this? (As I am ...
1
vote
1answer
42 views

$N$ is approximately linear in $d$ for $N^d=\frac12 e^{N}$

let us look at the function $N^d e^{-N}$, for each $d\in \mathbb{N}$. The graphs of the function for various values of $d$ show a striking phenomenon: the graph look parallel, and with a near-constant ...
1
vote
1answer
24 views

For what maximum positive $k$ is $2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$ true?

I am trying to find the maximum value of $k$ such that the inequality $$2n \sin^{2} \frac{\pi}{n} > \tan \frac{k\pi}{n}$$ is satisfied. I impose restrictions that $n \in \mathbb{Z}$ with $n \geq 5$...
4
votes
1answer
78 views

Does “the functions agree at infinity” mean anything?

I want a way to describe how two continuous functions $f,g \colon (X-x) \to Y$ might "share a limit" at the point $x$ when unfortunately neither of $\displaystyle \lim _{y \to x}f(x)$ or $\...
0
votes
1answer
29 views

Average of numbers converges, then what happens to the maximum

Let $\{a_n\}$ be a positive sequence of numbers such that $\displaystyle \frac1n\sum_{i=1}^n a_i \to a$ where $a>0$. Then can we say anything about the order of $\displaystyle b_n=\max_{i\in n} a_i$...
0
votes
0answers
40 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
5
votes
0answers
35 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
2
votes
1answer
58 views

Asymptotic behavior of integrals of Legendre polynomials

By definition $\int_{-1}^1 |P_n(x)|^2 dx = O(n^{-1})$. What about the other powers? Do we know how $\int_{-1}^1 |P_n(x)|^k dx$ behaves for any $k$? Maybe $O(n^{-k/2})$?
0
votes
1answer
33 views

Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
0
votes
0answers
31 views

I am looking a comparison of this computation and Riemann's approach for $lcm(1,2\ldots,x)$

Looking a comparison with a reasoning due to Riemann, I ask to me about the behaviour as $x\to\infty$ of the following arithmetical function $$ \left( \prod_{n\leq x}n^{-\mu(n)}\right)\cdot \left( \...
0
votes
2answers
74 views

Approximation of a quotient that involves the Lambert function.

I would like to find an asymptotic upper bound for $$\frac{-\ln n}{W(- \ln^{-c}n)}$$ where $c$ is positive and $W$ is the Lambert function. More precisely, I want something which dominates this ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
2answers
38 views

Big O for a $\cos$ series

I have to show that $ \sum_1^N \cos(nx) = O(\frac 1{|x|}), [-\pi, \pi] $, x different from 0. I really don't know how to show that. I obviously know that $\cos(nx)$ is bounded by $1$, I know what ...
1
vote
0answers
35 views

Products of $k^{\mu(k)}$, where $\mu(n)$ is Möbius function, and the Prime Number Theorem

We can write $$e^{-\Lambda(n)}=\prod_{d\mid n}d^{\mu(d)},$$ where $\mu(n)$ is the Möbius function and thus $\Lambda(n)$ is von Mangoldt's function. Then taking the product from $1$ to $N$ we've for ...
0
votes
1answer
19 views

Simple Sigmoid function that levels off at specific points

I need to construct a simple Sigmoid function that levels off at specific values of x, as in this curve: What is the most simple Sigmoid function that I can use ...
-2
votes
5answers
100 views

Hello. I need to show that $\sqrt n$ grows faster than $(\log n)^{100}$ [closed]

Is there an easy way to show that $$\lim_{n\to \infty}\frac {(\log n)^{100}}{\sqrt n}=0 $$
0
votes
1answer
13 views

Which one is asymptotically larger?

The question is to find out which among $n^\sqrt{n}$ or $n^(log_2 n)$ is asymptotically larger? Now as a solution I read somewhere that if we take log on both sides and then compute which one is ...
0
votes
1answer
46 views

Determine numerical infinity for Schrodinger equation $−\psi''(z) − (iz)^ N \psi(z) = E\psi(z)$

Consider the following one dimensional Schrodinger equation within the complex plane of $z$ $$ −ψ''(z) − (iz)^ N ψ(z) = Eψ(z). $$ where $N$ can be any real number, the boundary condition is $ψ(z) → 0$ ...
0
votes
0answers
17 views

Asymptotic growth of $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$

Can you give a solution or a hint for finding asymptotic bound for following recurrence relation: $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$ I know from the source of the problem that it is $\...
1
vote
2answers
46 views

If for some $n\in\mathbb{N}$, $\lim\limits_{x\to\infty}\frac{f(x)}{x^n}$ exists, then $f$ is rational

I don't know if this statement is true. Let $F$ be a function and suppose $n>0$, $n\in\mathbb{N}$ is the greatest such that there exists $L\mathbf{\neq 0}$ such that $\lim\limits_{x\to\infty}\frac{...
2
votes
0answers
36 views

Asymptotic distribution of zero-drift Geometric Brownian Motion as $t \to \infty$

If we fix the drift at $\mu = 0$, then my geometric brownian motion will have stationary mean, but it seems that the variance will grow without bound. What does the limiting distribution look like for ...
0
votes
0answers
9 views

Rate of expected value of $\mathcal{O}_p$

This is certainly very basic but what is the rate of the expected value of a random variable that is bounded in probability. For example, let $X_n = \mathcal{O}_p (a_n)$ is it true that $\mathbb{E} [...
0
votes
1answer
14 views

The Big O Notation and the Thetha Notation

I was instructed to find whether $$x*⌈x⌉*⌊x⌋$$ is$$ O(x^3) $$ or $$Big Thetha(x^3)$$ I tried to do a solution by cases, and i got : if x is not an integer, $$x=b+є$$ $$⌈x⌉=b+1$$ $$⌊x⌋=b$$ Then $$x*⌈x⌉*...
0
votes
0answers
22 views

Linear combination of asymptotic series

I need to compute an expression of the form \begin{equation}J=\sum_{k=0}^N a_k F_k(z)\end{equation} where z is a large parameter, and a_k are easily computable (k and z-dependent) coefficients. I ...
3
votes
1answer
41 views

Which singular perturbation method should be used for this system?

Consider the system $$ \varepsilon \dfrac{dx}{dt} = -(x^3 - ax + b)$$ $$ \dfrac{db}{dt} = x - x_a$$ where $\varepsilon \ll 1$. Applying regular perturbation methods isn't suitable because when $\...
-1
votes
1answer
25 views

Big O notaion O(n) and logaritms [closed]

Can someone explain me the subjects Big O notation and logarithms please? I can't understand those subjects For example if I have a question like this: recall that logan is the power to which you ...
1
vote
0answers
22 views

Finding asymptotycs of partition function

I have been stuck in this problem and have no idea of how to solve it. I have a hint from the book but don't really see how to use it. Any suggestion or hint would be really appreciated. Thanks! ...
3
votes
1answer
47 views

Verifying a step in the prime number theorem

This is an excerpt from Shapiro, "Introduction to the theory of numbers": Suppose that we have an estimate of the form $$|R(x)|\le \alpha x$$ valid for all sufficiently large $x$ (say $x\ge x_2$). ...
0
votes
0answers
21 views

Asymptotic upper bound for recurrence relations

The question is to find asymptotic upper bound for recurrence: (1) $T(n)=(T(n/2))^2$ and (2) $T(n)=(T(\sqrt{n}))^2$ with $T(n) = \text{n for n} \leq 2$ I think I will be able to find the ...
0
votes
1answer
32 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: $T(n) = ...
0
votes
0answers
19 views

Big O notation question (conceptual)

In my class, we have defined that $$ f(x) \ll g(x) $$ on $A$ if there exist a strictly positive c such that $$ |f(x)| \le cg(x) $$ for every $x$ on $A$. I'm a bit confused. Say that $ f(x) = x$ ...
3
votes
2answers
89 views

Prove that the value of the constant $C$ must be $1$

After proving the prime number theorem in class, our professor directs us to a remark by Lagrange that for large values of $x$, $\pi(x)$ is approximately equal to $$ \frac{x}{\log x - B}. $$ (This is ...
0
votes
1answer
63 views

Prove that $n! = O(n^n)$

I thought $n^n$ was greater than $n!$. How would I go about proving this? I have this so far: Assume that $P$($n$) is true $n!$ = O($n^n$) Assume that $P$($n+1$) is also true $(n+1)! ...
-1
votes
1answer
37 views

Prove little-o example [duplicate]

Let $f(x)=\log x$, and $g(x)=x^i$, where $0<i<1$. How can I correctly proof that $f(x)=o(g(x))$? Try 1: By the definition of little-o, a function is little-o of other function if $|f(x)|\leq C|...
2
votes
1answer
24 views

How to prove that $f(x)$ is $O(x^i)$ for a general polynomial

Let $f(x)=a_ix^i + a_{i-1}x^{i-1} + \ldots + a_0$ where $a_i>0$. How can I proof that this general polynomial with real coeficients is $O(x^i)$ using the Big-O notation theory. Try 1: I thought ...
0
votes
1answer
15 views

$\lim_{n\to\infty}\frac{f(n)}{h(n)}$ if $f\in o(g)$ and $g\in O(h)$

I would appreciate it if anybody could check my attempted solution to this question. I'm guessing since the question says 'values' rather than 'value' that I haven't finished the question. So if you ...