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

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
1
vote
1answer
318 views

Time Complexity for $T(n) = T(\sqrt{n}) + 1$ [duplicate]

$$T(n) = T(\sqrt{n}) + 1$$ I am trying to find the time complexity of the given equation. I tried everything that I know but I could not find the answer. What I've tried: $k = lg(n)$ and $n=2^k$ -> ...
3
votes
1answer
157 views

Explanation for Terry T. post

I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N ...
1
vote
3answers
2k views

Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
1
vote
3answers
101 views

Time Complexity in $\theta$ Notation

$$T(n) = 2T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 5$$ What is the time complexity of the given algorithm in $\theta$ notation. Thanks in advance.
1
vote
0answers
36 views

Frechet differentiability, asymptotic normality

I try to prove the asymptotic normality from the Frechet differentiability. Consider $$T(G)-T(F)=L_{F}(G-F)+o\left(d_{\star}(G,F)\right)$$ and ...
0
votes
1answer
39 views

Proving if equation is $O(\log n)$

How do I prove if \begin{equation} 2\log(n^{2}\log n) = O(\log n) \end{equation} is true? I began by trying to find a $C$ where \begin{equation} 2\log(n^{2}\log n) < O(\log n) \end{equation} ...
0
votes
2answers
107 views

Why isn't $\log(n!) \leq O(n\log n)$? [closed]

Why isn't $\log(n!) \leq O(n\log n)$? I know that $\log(n!)$ is of $\Theta(n\log n)$ but why can't a function that is of $\Theta$ be $\leq$ than a function that is $O$ of the same parameter? Isn't ...
1
vote
1answer
283 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
0
votes
1answer
114 views

Use algebra of Big-O notation to express tan($z$)

We can use the definition of Big-O notation to simply prove that $\sin(z)=z-\frac{z^3}{6}+O(z^5)$ as $z\rightarrow 0$, $\cos(z)=1-\frac{z^2}{2}+O(z^4)$ as $z\rightarrow 0$ and ...
2
votes
2answers
89 views

Is it true that $(2^n+n^2)(n^3+3^n)$ is $O(6^n)$?

$(2^n+n^2)$ is $O(2^n)$ and $(n^3+3^n)$ is $O(3^n)$, therefore I conclude that $(2^n+n^2)(n^3+3^n)$ is $O(2^n*3^n)=O(6^n)$
-1
votes
1answer
111 views

Proving Big O(1) [closed]

How do I determine if the below is true or false? \begin{equation} 17^{100} + \frac{1}{n} = O(1)? \end{equation} I have tried using the c and No method but still can not come up with a solution.
0
votes
0answers
47 views

Proving big-O asymptotics for inverted matrices

Suppose $A,B:\mathbb{C}\rightarrow\mathbb{C}^{n\times n}$ are non-constant and invertible as matrices everywhere, and satisfy that $B$ is an entire holomorphic mapping and $A(z)=B(z)+O(1/z)$ as ...
0
votes
1answer
60 views

Proving Big Θ of summations with exponentials

I have been working on this problem but have had a hard time understanding how to prove it as True, which I believe it is. ...
1
vote
2answers
446 views

Derivative of $n^{\log n}$?

What would be the derivative of $n^{\log n}$? I have to prove that $(\log n)^n$ = $\omega$($n^{\log n}$). I am trying to implement L'Hopital rule.
2
votes
0answers
33 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
6
votes
0answers
95 views

Asymptotic property of integral involving Bessel function.

Consider the following integral $$ I(s)=\int_{0}^{\infty}{J_{\frac{n-2}{2}}}(sr)r^{A+1}(e^{-r^{2\alpha}}-1)dr, $$ where $J_{\frac{n-2}{2}}$ is the Bessel function of order ${\frac{n-2}{2}}$, $s, A, ...
1
vote
1answer
83 views

Maximizing edges in directed acyclic graph

Question: What is the maximum number of edges in a non-transitive directed acyclic graph on $n$ vertices? Here nontransitive means, if there is an edge between $A$ and $B$, and an edge between $B$ ...
0
votes
1answer
277 views

Asymptotic Notations (Big Theta)

For an assignment, I have the following question: For all functions $\;f, g : \mathbb{N} \to \mathbb{R}^+$ from positive integer numbers to nonnegative real numbers, let the running time $T(n)$ of an ...
3
votes
5answers
120 views

Is $n! = o(n^n)$?

Intuitively, it seems that $n! = o(n^n)$. We can associate each value in the factorial with a single $n$ to divide by, so $\lim_{n \rightarrow \infty} \frac{n!}{n^n}$ seems to be $0$. However, I ...
0
votes
1answer
57 views

How to prove statement about $\mathcal{O}, \Theta$ and $\hbox{o}$?

For a given function g, Prove that $\hbox{o}(g) \neq O(g) - Θ(g)$. Thanks for the help in advance
0
votes
1answer
26 views

Using log of function to determine orders of growth

If I have functions $f(n)$ and $g(n)$ and I would like to determine $f(n) \in \Omega g(n)$ and/or $f(n) \in \Theta(g(n)$. Does proving $\log(f(n)) \in \Omega \log(g(n))$ imply $f(n) \in \Omega g(n)$? ...
0
votes
1answer
42 views

Neglecting constants in big O notation

I'm just starting to learn big O notation and there's one thing in particular that bothers me. Say $f(n) = O(g(n)+c))$, where c is a constant. To my understanding, $f(n)$ can just be represented as ...
4
votes
1answer
163 views

Estimating integrals involving $\pi(x)$

While solving an exercise in analytic number theory, I ran into difficulty of estimating an integral of the form $\displaystyle\int_{1}^{x} \frac{\pi(t)}{t} dt$ where $\pi(x)$ is the prime counting ...
1
vote
3answers
245 views

Is it true that every function f satisfies $f(2n) = Θ(f(n))$?

I am trying to determine if this statement is correct or not: Every function f satisfies f(2n) = Θ(f(n)) Where, as I understand it, $f(2n)$ cannot be bounded by ...
1
vote
2answers
40 views

Properties that hold when $f = \mathcal{O}(g)$

This is a homework problem. There are two questions where the answers seem intuitive, but even if I were correct in assuming they were true, I'd still need to provide a proof: When $f(n) = ...
2
votes
1answer
123 views

Mysterious subleading corrections to sums with internal dependence on limit

Is there a standard method for finding expansions in $N$ of sums like $$S(N)=\sum_{n=0}^N \sqrt{N^2-n^2}$$ beyond the first term? It is easy to compute here that $$S(N)=N^2 \int_0 ^1 \sqrt{1-x^2} ...
1
vote
0answers
25 views

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)…(n-k+1) \approx n^k$

Prove that if $k^2=o(n)$, then $n(n-1)(n-2)...(n-k+1) \approx n^k$ Do I start by dividing both sides by n^k and collecting terms, perhaps? Not sure. Not entirely sure about the relevance of ...
0
votes
2answers
139 views

Finding tight bound for a function

Suppose we are given a rational function $f(n)=\frac{p(n)}{q(n)}$ and need to find g(n) that satisfies: $f(n) \in \Theta(g(n))$. Does g(n) need to be one of $n^c, log n, n log n$ or can it be, in this ...
3
votes
2answers
341 views

Why does taking logs of exponential functions affect growth rate?

We were doing a quick review of undergrad topics the other day in my grad Algorithms class and the professor asked a simple question: Which grows faster, $2^n$ or $3^n$? Everyone was quick to agree ...
0
votes
2answers
47 views

Are big-theta, Big-O, etc. all representative only of GROWTH of the function?

For example, $2^{n-1}$... is that $\Theta(2^n)$? it GROWS the same... but it in actuality will never be greater than or equal to the actual 2^n function, for example. $\log_2(n)$, is that ...
1
vote
1answer
92 views

Prove that $f(n)$ is in $\Theta(g(n))$

Suppose $f(n) = 1^k + 2^k + \ldots + n^k \;$ and $\; g(n) = n^{k+1}.\;$ Prove that $\;f(n)\in \Theta(n^{k+1})$. My understanding is that we have to find $C_1, C_2 \gt 0$ such that: ...
1
vote
1answer
63 views

asymptotic of a product

So the question that I'm working on is the following. Show that $\Pi_{p\leq z}(1-\dfrac{1}{p})=\dfrac{C(1+\mathcal{o}(1))}{\log z}$. First off I take logs and just work with the sum and thisis what ...
1
vote
1answer
39 views

Big Omega for values going to zero

Usually, at least in Computer Science, $f(x) = \Omega(g(x))$ if $ \exists C > 0, \exists x_0 : \forall x \geq x_0 : f(x) \geq C g(x)$ i.e. for large values of x, $f(x)$ is at least as big as some ...
3
votes
1answer
27 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
0
votes
3answers
44 views

What is the correct notation for simplifying O notation?

For instance I want to say something like: "Here is the resulting runtime: $$\sum_{x}^{n}\sum_{y}^{x} (1) = \frac{n(n+1)}{2} \implies n^2 \implies O(n^2)$$" But what is the proper way to state this ...
1
vote
1answer
45 views

Asymptotic Expansion in zero of $\frac{1}{\ln(1+x)}$

On wolfram the expansion is: $$\frac {1}{x} + \dfrac{1}{2} ...\,.$$ But I don't understand from where it outside comes the $\frac{1}{2}$ thanks
3
votes
4answers
226 views

Algorithm Analysis: How to simplify a summation leading up to a maximal term?

Okay so I have a summation which goes: $$\sum_{i=1}^{n^3} 3i^2\cdot\log(i)$$ My goal is to find the order of the function, not the exact summation amount. I have found the order of it by writing ...
2
votes
3answers
88 views

Determine appropriate $c$ and $x_0$ for Big-O proofs.

"Prove that $f(x)$ is $O(x^2)$:" $$f(x) = \frac{x^4+2x-7}{2x^2-x-1}$$ Let $c=10$ (addition of coefficients of the numerator less the addition of coefficients of the denominator), and $x_0 = 1$ (the ...
2
votes
2answers
407 views

Question about the “master theorem” of recurrences - no “$b$” term

I'm using the master theorem to find the asymptotic run time of recurrences. For example, for a $T(n) = 4 T(n/5) + n^1$ I find that $T(n)$ is $\Theta(n^1)$, or, simply, constant time, via the set of ...
0
votes
2answers
60 views

Prove that so and so is $O(x^4)$

Given $f(x) = x^3 + 20x + 1$, how would I prove this is $O(x^4)$? By definition, the function is $O(x^4)$ iff $f(x) <= cn^4$, where $c$ is some constant. However, I'm not sure where to go from ...
0
votes
1answer
112 views

Asymptotic (Big-O notation) for given expressions

Basically I need to convert these expressions into asymptotic notation. Now from what I read online, I believe number 1 should be correct, however, I'm not so sure... 1) $5x^3 - x^2 + 1$ ...
1
vote
1answer
42 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
1
vote
1answer
103 views

Numerical Analysis - Richardson Extrapolation

Question: Suppose that N(h) is an approximation to $M$ for every $h > 0$ and that $M = N(h) + K_1 h + K_2 h^2 + K_3 h^3 +\cdots$, for some constants $K_1, K_2, K_3,\cdots$. Use the values $N(h), N( ...
2
votes
1answer
135 views

Asymptotic notation for logarithmic function

Can anyone explain to me how $$ f(n) = n^{0.999999} \log n = O(n^{0.999999} n^{0.000001}) $$ ?
2
votes
1answer
49 views

Can I move “little o” into an exponent on an asymptotic bound

I want to make really sure that I am not making a mistake here, although I generally don't have problem with asymptotics. I have proven that a certain function $f(n)\in o(2^n)$. Well actually I ...
0
votes
0answers
70 views

How to check if a function is negligible?

Let $\epsilon(x)$ be a negligible function. Let $p$ be a polynomial such that $p(k) \geq 0$ for all $k > 0$. What can we say about $\epsilon(p(k))$? Is this a negligible function? If yes, ...
1
vote
1answer
942 views

Asymptotic Matching for boundary layer problem

The question asks to find a global approximation to the leading order of $\epsilon$. $\epsilon y'' + xy' + \epsilon y =0$, with boundary conditions $y(0)=1,y(1)=-1$. I assumed it's a boundary layer ...
1
vote
5answers
337 views

What does this symbol “$\gg$” mean

I was reading a paper and came to a symbol as follows: "$\gg$" (e.g. $x\gg 5$). What does that mean? Is it larger than or has more information to mention? Thanks.
1
vote
2answers
68 views

Asymptotic probability of difference of two positive random variables

Assume I have two positive, iid random variables, $X$ and $Y$. I need to compute $P\{X-Y > u\}$. I was thinking of doing $P\{X > Y + u \} = P\{X > v\}$, where $v = Y+u$. (Reason: Since $Y$ ...