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

learn more… | top users | synonyms (1)

3
votes
1answer
361 views

Proving a function is big O

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)? Example: Prove that $x^n$ is $O(n!)$ for every real number $x$. My proof by ...
0
votes
1answer
525 views

Big O notation doubt f(n) = g(n)

If $$f(n) = g(n) = n $$ then Is $$f(n) = O(g(n)) $$ As far as I know it is according to the definition of Big-O notation. So, if this is the precondition then Is $$2^{f(n)} = O(2^{g(n)})$$ ? I ...
1
vote
2answers
212 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
3
votes
1answer
47 views

What's the relationship between $O(\log(x+y))$ and $O(\log(xy))$

Which of these bounds, $O(\log(x+y))$ and $O(\log(xy))$, is tighter? Or are they equal?
0
votes
0answers
58 views

Are the Prime Numbers $O(f(n))$ where $f(n)$ is some polynomial?

Are the prime number, denoted $ p(n) $, $O(f(n))$, for any polynomial $f(n)$?
1
vote
1answer
180 views

Simple random walk hitting time asymptotic behavior

Let $p(n,t)$ be the probability that a simple random walk starting at state $n$ hits $0$ within $t$ steps. How big can $p(n,t(n))$ get for large $n$ when $t(n) = o(n^2)$? It seems like maybe it could ...
0
votes
1answer
809 views

Working with the ~ (tilde) notation (asymptotic analysis)

For positive functions $f$ and $g$ on real domains, define $f(n) \sim g(n)$ to mean $\displaystyle\lim_{n\to\infty}\frac {f(n)}{g(n)}=1$. Given that $$\frac{n^{n+\frac12}}{e^{n-1}n!}\sim\frac ...
0
votes
1answer
32 views

Order of the solution to an IVP

Suppose you have the following IVP $$\dot{y}(t) = d_1 y^2 + d_2 \epsilon^{-1} y$$ with $y(0) = y_0$ and where $d_1$ and $d_2$ are two positive constants independent of $\epsilon$. What can you ...
2
votes
1answer
31 views

If $f(x_0+x)=P(x)+O(x^n)$, is $f$ $m<n$ times differentiable at $x_0$?

Let $f : \mathbb{R} \to \mathbb{R}$ be a real function and $x_0 \in \mathbb{R}$ be a real number. Suppose that there exists a polynomial $P \in \mathbb{R}[X]$ such that $f(x_0+x)=P(x)+ \underset{x \to ...
1
vote
2answers
47 views

The growth rate of the functions with respect to each other

There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$? Thank you.
1
vote
0answers
66 views

Asymptotic notation of the following function

I have two functions, $f(n)$ and $g(n)$, and I am trying to determine whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$. I am not sure about my answers. Help will be appreciated. a) ...
3
votes
1answer
34 views

Indicating the complexity of functions

I am not sure about my answer about the following question. Can anyone help? I try to express whether $f(n)$ is $O(g(n))$, $\Omega(g(n))$ or $\Theta(g(n))$, where $f(n)=n^{0,1234}$ and ...
9
votes
5answers
444 views

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $.

Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction. I get the intuition behind this question. Clearly, the given function isn’t even growing ...
1
vote
1answer
514 views

Rate of growth of exponential functions

I have difficulties about proving the following: Prove that exponential functions $a^n$ have different orders of growth for different values of base $a>0$. It looks obvious that when $a=3$ it ...
1
vote
2answers
289 views

Deciding whether a function is O(n), Ω(n), or Θ(n)

First of all, this is my homework question, i have my answers and i want to be sure whether i am missing something. I have difficulties about deciding whether f(n) is O(g(n)), Ω(g(n)), or Θ(g(n)): ...
1
vote
1answer
91 views

Asymptotic behaviour of a sequence

We fix $\alpha >0$, and we look for the asymptotic behaviour when $n \to +\infty$ of $$u_n=1^{\alpha n}+2^{\alpha n}+\cdots+n^{\alpha n}.$$ Any suggestion?
2
votes
3answers
83 views

Understanding $O$-notation and the meaning of $\Omega$

I am studying algorithms, and I have problems on the concepts from an exercise. Thank you so much! Which of the following equations lie in $O(n)$, $\Omega(n)$, $\Theta(n)$ and why. a. ...
3
votes
1answer
135 views

What happened to the Mertens constant in the strong prime twins conjecture ??

To estimate the amount of primes in an interval $\left(2,x\right)$ one might naively sieve by computing $ x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right)$ ...
14
votes
3answers
223 views

Sufficient bound to conclude limit has certain value. $\lim {\left( {\int_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $

I am trying to show that $$\lim {\left( {\int\limits_0^1 {{{dx} \over {1 + {x^n}}}} } \right)^n}=\frac 1 2 $$ Now, this can be done as follows. Using $x\mapsto x^{-1}$ we get that $$\int\limits_0^1 ...
1
vote
1answer
146 views

How do we show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$

Basically I'm wondering how I can show that $x^5y^3 + x^4y^4 + x^3y^5$ is $\Omega(x^3y^3)$. Any ideas? Thanks a lot!
1
vote
1answer
43 views

Limits of entire functions

Given an entire function $f \left(x \right)$, which entire function $g \left(x \right)$ is asymptotic to $f \left(x \right)$ as $x \rightarrow \infty$ and asymptotic to $1$ as $x \rightarrow 0$? When ...
1
vote
2answers
64 views

Roots of the equation $I_1(b x) - x I_0(b x) = 0$

I'm interested in the roots of the equation: $I_1(bx) - x I_0(bx) = 0$ Where $I_n(x)$ is the modified Bessel function of the first kind and $b$ is real positive constant. More specifically, I'm ...
2
votes
1answer
376 views

Big O notation: relation between Omega and Big O?

Can I do this if I need to proove something for $\Omega$: $f(n) \in \Omega(g(n)) \iff g(n) \in O(f(n))$?
0
votes
1answer
92 views

For $f(n)$ find a simple $g(n)$ such that $f(n)=\Theta(g(n))$

I have to find a specific $g(n)$ such that $f(n)=\Theta(g(n))$. $$f(n) = \sum_{i=1}^n3(4^i)+3(3^i)-i^{19}+20$$ I suppose that this can be solved as integrating this formula, but i don't know how and ...
5
votes
4answers
1k views

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could ...
1
vote
0answers
82 views

Bounding the product of a sequence

I am trying to find an upper bound for the following sequence: $$(1-p_1)(1-(p_1+p_2))\cdots(1-(p_1+\cdots+p_n))$$ with $n$ groups to multiply. I have written it like this: $$\prod_{i=1}^n \left({1 ...
2
votes
2answers
148 views

Asymptotic behavior of entire functions

Which entire function $f\left(x\right)$ goes asymptotically to $\dfrac{e^{-x}}{x}$ as $x$ goes to infinity with $x$ positive? That is, $\left(e^{-x}/x \right)/f \left(x \right) \rightarrow 1$.
0
votes
1answer
138 views

Every uniformly continuous real function has at most linear growth at infinity

Assuming $f:\mathbb R\to\mathbb R $ be an uniform continuous function, how to prove $$\exists a,b\in \mathbb R^+ \quad \text{such that}\quad |f(x)|\le a|x|+b.$$
1
vote
2answers
104 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
0
votes
1answer
79 views

Asymptotic of a particular integral

This is in relation to my question here. I am reading from this paper and specifically the doubt is from a statement on page 177. Suppose $\alpha\in(0,2)$ and $t_i=ih$ for some fixed $h>0$ and ...
0
votes
1answer
85 views

What is a basic definition for Big Oh, and it's component parts?

this is a question that somewhat straddles the boundaries of computer science (data structures and ). I'm mostly fine with data structures, until encountering big oh notation.. at which point my head ...
1
vote
2answers
117 views

Θ(n) + O(n) = ? (recurrence equation)

If I have a recurrence equation like: T(n) <= T(n/2) + Θ(n) + O(n) Is the above expression equal to: T(n) <= T(n/2) + Θ(n) Or is that expression equal to: T(n) <= T(n/2) + ...
1
vote
1answer
536 views

Meaning of algebraic decay

I am reading the paper here and I am running into a few roadblocks. One of them was resolved here and now I am stuck at another. (Pg 177) Suppose $\alpha\in(0,2)$ and $t_i=ih$ for some fixed $h>0$ ...
0
votes
1answer
754 views

solving recurrence relation by substitution method and find asymptotic bound

Solve the following recurrence relations and give a bound for each of them. $T(n)= 2T(n-3)+1$ $T(n) = 5T(n-4)+n$
0
votes
1answer
1k views

Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$

Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Here's what I've come up with, but I'm not ...
3
votes
1answer
314 views

Techniques for asymptotic growth comparison between complicated expressions

For the following functions: $$\frac{2^n}{n + n \log n}$$ and $$4^{\sqrt{n}}$$ I'd like to compare their asymptotic growth as $n \to \infty$. Is there any other way to do that other than using ...
0
votes
1answer
67 views

Finding the limit of a summation in order to find Asymptotic Comlexity [duplicate]

I havent done this in a while so I was hoping someone can remind me how to do this, I need to find the limit of this summation: $$\lim_{n \to \infty}{\displaystyle\sum_{k=1}^{n} \frac{1}{k^2}} $$ ...
2
votes
1answer
367 views

Big o notation $( n \log n + n \log(n^{\log n}))$

I'm trying to transform this: $$n \log n + n \log(n^{\log n})$$ into big O notation. I can't get to reduce the right part of the addition... Neither of these work: $$n^{\log n} ...
0
votes
1answer
3k views

What does it mean when you say that the function is bounded?

What I figured is that it means that the function has an upper bound, however I came across this text: Here since g(x) either equal or less to f(x), |g(x) / f(x)| must be bounded right? Since the ...
3
votes
1answer
113 views

BigO sorting complexity help

Given a bit sequence of length a, what is the minimum number of comparisons needed to determine if it contains a pair of consecutive 1's in BigO notation
2
votes
1answer
365 views

Lower bound for matrix sorting?

Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem. I found that it is $O(n^2logn)$ by just ...
11
votes
1answer
137 views

Asymptotic behavior of $|f'(x)|^n e^{-f(x)}$

Let $f$ be a strictly convex function on $\mathbb R$, $f'' \geq C > 0$. Let $n$ be a positive integer. What can we say about the growth rate of $|f'(x)|^n e^{-f(x)}$ as $x\rightarrow \infty$? Must ...
1
vote
1answer
129 views

Difficulty proving / disproving the following equalities relations ( Big Ω)

I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations. Here are the three relations: $ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $ ...
2
votes
3answers
68 views

Growth of $\frac{1}{m-1} \sum_{t | m-1} t \varphi(t)$

I am interested in bounds for $$S_m = \frac{1}{m-1} \sum_{t | m-1} t \varphi(t)$$ as $m$ gets large.
0
votes
2answers
538 views

Asymptotic upper bound in Big-O for $T(n)=T(n-1)+3n-5$. Proof using induction

I need to prove using induction Asymptotic upper bound in Big-O for $$T(n)=T(n-1)+3n-5$$ So I tried expanding $$\begin{align} T(n) &= T(n-1) + 3n - 5 \\ &= T(n-2)+ 2(3n-5) \\ &= T(1) ...
0
votes
1answer
69 views

if $a= O(N^2)$, can I also say $a=O(N^4)$?

if $a=O(N^2) $ then according to the big oh definition I didn't see why we can't say $a= O(N^4)$ or $= O(N^8)$
2
votes
1answer
84 views

Prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$

How do I prove $f(n)=n \log{\log{n}} \notin \Theta (n^k)$ for any $k$? I have no idea where to start but I tried plotting the graph in Google and noticed that $\log{\log{n}}$ is very close to 0. But ...
0
votes
1answer
190 views

Asymptotic Notation more specifically, Big-O notation

How the functions in the class $O(d)^d$ and $\epsilon^{1/O(d.4^d)}$ looks like..? where $\epsilon$<1. I am really confused with this complicated Big-O notations Can you please help me out.
1
vote
0answers
30 views

Evaluating a simple sum bound

I'm trying to evaluate and prove a simple statement but It seems really raw/bad solution. I would like to advise with you if this is the right way because It is really getting more complicated than It ...
1
vote
1answer
44 views

Simplifying Equation - Asymptotic analysis

The textbook I'm using for the course Introduction to Algorithms class has the following statement in it: The equation of such a line is $\log (T(N)) = 3 \log N + \log a$ (where a is a ...