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
0answers
25 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
votes
0answers
20 views

For $\Theta$ notation which statements are true? [on hold]

Assume an algorithm runs in $\Theta(n^2)$, then which one of the following asymptotic notation for it? $O(n^3)$ $O(n^2)$ $\Omega(n^2)$ All above are correct.
1
vote
1answer
49 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
44 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
22 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) = ...
0
votes
0answers
11 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
11 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
37 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 ...
1
vote
4answers
53 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
39 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 ...
4
votes
1answer
76 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
26 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} ...
0
votes
0answers
12 views

How can I prove this formula for big theta notation? [closed]

How can I prove this proberty $$\max(f(n)+h(n)) = \Theta (f(n)+h(n))$$ where $\Theta$ is the big theta notation and max is the maximum between functions $f(n),h(n)$?
-1
votes
0answers
11 views

Is f(n1 x n2) = Θg( n1 x n2 ) true?(Discrete mathematics, Algorithm)

I have a question about Theta Notation. For X={1,2,3 .....} n1 and n2 are elements of X If f(n1) = Θg(n1) and f(n2) =Θg(n2), then is f(n1 x n2) = Θg(n1 x n2 ) true? My speculation is that for n1 x n2 ...
0
votes
0answers
33 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 ...
4
votes
0answers
27 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
52 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
25 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
65 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
34 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
30 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
16 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
95 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
40 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
16 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 ...
2
votes
0answers
34 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
7 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
13 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 ...
0
votes
0answers
14 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
39 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
19 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
19 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
31 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: ...
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
84 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
61 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
31 views

Prove little-o example

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 ...
2
votes
1answer
23 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
13 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 ...
0
votes
1answer
19 views

Proving equation using formal O(f(n)) - step by step?

I have huge problems showing whether example like this: is true or false using formal definition of Big O. How can I solve such problems step by step? I understand that formal definition of ...
1
vote
1answer
32 views

Asymptotic behavior of Fourier transform and Hölder condition

I'm trying to solve this question. Following the hint, the Fourier inversion formula gives me : $$ \big| f(x+h) - f(x)\big| = \left| \frac{1}{2\pi} \int_{-\infty}^\infty \widehat{f}(\xi) ...
4
votes
1answer
61 views

The behaviour of $\sum k^a 2^k$.

Let $a$ be a real number, I want to find a simple equivalent (or if it is possible, an asymptotic expansion) of $$\sum_{k=1}^n k^a 2^k.$$ I believe that the sum is $\sim n^a 2^{n+1}$ (tried many ...
8
votes
0answers
99 views

If $n={k^2 \choose k}$, then what is $k$?

Given that: $$n={k^2 \choose k}$$ what is $k$ as a function of $n$? So far, I have found the following approximation: $$ n \approx (k^2)^k = (k^k)^2 $$ $$ \sqrt{n} \approx k^k $$ If we take this ...