Tagged Questions
0
votes
0answers
13 views
Is it possible to interpret condition $\sum_{1\leq i < j \leq n }r(|i-j|)=O(n^2)$ as $r=O(f(|i-j|))$?
Given a sum: $$\sum_{1\leq i < j \leq n }r(|i-j|)=O(n^2)$$ can I express the conditions for $r$ depending on $|i-j|$, kind of:
$$r=O(f(|i-j|))$$
Thanks in advance!
2
votes
2answers
36 views
Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply $\frac{f(\epsilon)}{\epsilon}=o(1)$?
I have the following homework question:
Does $f(\epsilon)=o(\epsilon\ln(\epsilon))$ imply
$\frac{f(\epsilon)}{\epsilon}=o(1)$ ?
It doesn't seem correct to me, using the definition I could only ...
5
votes
2answers
50 views
Prove $\log x!$ is $\Omega (xlogx)$
Find a positive real number $C$ and a nonnegative real number $x_o$ such that
$Cx$$\log x$ $\leq$ $\log x!$ for all real numbers $x > x_o$.
I tried to expand $\log x!$ into $\log 1 + \log2 +\log3 ...
-1
votes
3answers
44 views
Calculate big-$\Theta$ for $T(x) = \log(x2x!)$
$T(x) = \log(x2x!)$
use the property of log, $\log(x2x!)$ is equivalent to $\log(2x) + \log(x!)$
My approach is to prove big-$O$ and big-$\Omega$ for $T(x)$,then big-$\Theta$ just follows.
If I ...
3
votes
3answers
74 views
Does $n n^{1/n} =O(n)$?
I was asked does $n n^{1/n} =O(n)$ ?
I can see that the left hand side is always bigger than $n$ but how would you prove the equality is false?
2
votes
1answer
30 views
simplifying an asymptotic expression
I have this expression in a statistics book, namely $nh(f(x) +o(1)+O_p(1/\sqrt{nh}))$. Where $f$ is a density function. Now, this expression is equal to $nhf(x)\{1+o_p(1)\}$. Note, that $n\to ...
1
vote
4answers
99 views
Error in “proof” of $n^2 \in O(n)$.
I need some help. I have homework:
I need to disprove that $f(n^2)$ belongs to $O(n)$.
Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
2
votes
1answer
76 views
How to prove that $\lim_{x\to \infty} x/2^x = 0$
I need to prove that $\lim_{x\to \infty} x/2^x = 0$
I'm not sure I did it right:
I applied L'ôpital's rule and obtainded: $\lim_{x\to \infty} \dfrac{1}{2^x\ln2}$
and this is equal to ...
1
vote
4answers
69 views
How to prove that $\lim_{n\to \infty} (n^k/2^n) = 0$?
I'm having a hard time trying to prove this statement.
$\lim_{n\to \infty} (n^k/2^n) = 0$
k is a positive number.
Please, help me.
Thanks in advance.
1
vote
1answer
48 views
How to prove that $n^k = O(2^n)$
I'm having issues trying to prove this.
The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ ...
0
votes
1answer
61 views
Solving a recurrence realtion using backward substitution.
So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P
I start off with this ...
0
votes
1answer
93 views
Solving Recurrence Relation with Forward Substitution
I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with
$$
T(n) = 4T(n/3)
$$
For all $n > 1$ ...
3
votes
4answers
139 views
Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$
Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$:
$$
T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)
$$
...
0
votes
1answer
77 views
Proof of limit ratio theorem
My professor defines the Limit Ratio Theorem as follows:
Assume that $\displaystyle\lim_{n \mapsto \infty} \frac{f(n)}{g(n)}=c$, where $c$ is a constant or $\infty$.
If $0 \leq c < ...
1
vote
0answers
68 views
Large Deviations Problem
Let $\left(X_n\right)_{n\geq 1}$ be i.i.d random variables on $\left(\Omega,\mathcal A, \mathbb P\right)$, $X_1$ with mean $\mu$, and
$$
L(\lambda) =
\begin{cases}
\log\mathbb E\left(e^{\lambda ...
1
vote
3answers
49 views
how to proof this big-oh statement?
I have a question on my homework which is:
Prove that if $f(x)=O(g(x))$, and $g(x)=O(h(x))$, then $f(x) = O(h(x))$
I am not to sure how to prove this. This is my attempt. Is it good enough or am i ...
10
votes
1answer
141 views
Calculate Asymptotics of Integral?
Let $f$ be a continuous function on $[0,1]$. How do I calculate the asymptotics, as $n\rightarrow\infty$, of
$\displaystyle \int_{[0,1]^n}f\left(\frac{x_1+...+x_n}{n}\right)\text d x_1...\text d ...
0
votes
1answer
66 views
Big O Solving recurrences
Hello So I am having trouble solving this recurrence: $t(n) = t(\sqrt{n}) + 1$. The master method does not apply here. Ive done some research and it seems you have to manipulate the domain and ...
0
votes
0answers
48 views
How can weakly/strongly decreasing or increasing approximate sums be explained?
I'm reading around big O to get some concept about performance for data structures. The mathematics book recommended by the open book ~ maths for computer science
In the book (pg 456) part of the ...
0
votes
1answer
47 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 ...
0
votes
1answer
66 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
1answer
104 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} ...
1
vote
1answer
50 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) $
...
1
vote
0answers
24 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 ...
0
votes
1answer
173 views
Dominant term and Big Omega
For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation.
$$n^3+n^2\log_2(n)+n^3\log_2(n)$$
So, I ...
0
votes
1answer
61 views
What is the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$?
I have to find the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$. So I have to find the limit of the function when $x$ approaches zero. In my textbook it says that the vertical asymptote does not ...
2
votes
2answers
70 views
How to show $n! = \omega\big((\frac{n}{3})^{n+e}\big)$?
I'm learning some mathematics by myself and get stuck. The problem is to show that
$n! = \omega\big((\frac{n}{3})^{n+e}\big)$, $\omega$ is the asymptotic notation.
It's from the Problem Set 7 of MIT ...
0
votes
0answers
57 views
Big O - proving that an estimate is correct
I recently submitted this for homework. The question asked to give a big-O estimate for (1) below. I have included the feedback in bold. It seems the solution I proposed lacked a proof and I unsure ...
0
votes
0answers
123 views
Solve recursion formula using Recursion Tree concept
I'm trying to figure out an important idea regarding solving Regression formulas / Recurrsion formulas using the Recursion Tree idea.
I will first write down the exercise and then I'll try to explain ...
0
votes
1answer
65 views
Prove that the little-o definition doesn't hold for two function (f and g)
I need your help with the following statement:
Show there exist two function $f(n), g(n)$ such that meet the following definition:
$g(n) = O(f(n))$ and $f(n) \ne O(g(n))$
But don't meet the ...
0
votes
2answers
84 views
Some Big-O complexity definition proofs
I'm trying to prove (by definition) the following but to no avail:
$n^{n/2} \ne O(3^{n/2}) $
$n! \ne O(3^n)$
$(n-b)^a = \Theta(n^a)$
$a,b $ are both constants whereas $a > 0 $ and $b$ ...
0
votes
2answers
193 views
Little-o proof by definition
I'm trying to figure out how to prove the following but to no avail.
Given the following functions :
$f(n) = n^3 -4n$
$g(n) = 5n^2 + 3n$
I have to show that $g(n) = o(f(n))$
by definition, that ...
0
votes
3answers
59 views
Big-O compared to a new Operator
I'm trying to figure out a new operator compared to the Big O.
Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $ c > 0 $ ...
1
vote
1answer
82 views
Asymptotics for sum of binomial coefficients
Could you give me a hint how to find $c$ in the asymptotic for the sum:
$$
\sum_{k=0}^{\lfloor {n}/{2} \rfloor}\binom{n-k+1}{k}=(c+o(1))^n
$$
and for
$$
\max\limits_{a\leq ...
0
votes
1answer
60 views
How to find asymptotes
I'm supposed to find asymptotes for $x\cdot\arctan(x)$ for a homework assignment.
Are there any theorems regarding this I can utilize to find the equation for the asymptotes, or is this one of those ...
2
votes
1answer
150 views
Asymptotic behavior of $\sum\limits_{k=2}^{m}\frac{1}{\ln(k!)}$
The task is to find asymptotic behavior of sum:
$$\sum\limits_{k=2}^{m}\frac{1}{\ln(k!)}$$
when $m\to\infty$.
Any help with solving this one?
1
vote
1answer
65 views
Prove the asymptotic for the sum
I need to prove, that
$$
\sum_{k=1}^n{k^p\ln^qk} \sim \frac{n^{p+1}}{p+1}\ln^qn
$$
where $p > -1$.
I tried to use Stolz–Cesàro theorem to show that:
$$
\lim_{n\to ...
1
vote
1answer
111 views
little o notation with natural logs
I'm having trouble with little o notation.
Help me show that:
$2(n^2 + 100n)\log^5n = o(n^2\sqrt{n})$.
It is the last hwk on my sheet and I don't understand it, if someone can help me with ...
1
vote
0answers
112 views
Big-O notation questions on estimates
I have some questions to prepare for exam on Big-O as follows:
$2^{2n} = O(2^n)$
$40^n = O(2^n)$
$(2n)! = O(n!)$
$(n+1)^{40} = O(n^{40})$
Please could someone advise if my attempted solutions are ...
2
votes
2answers
51 views
Asymptotic for implicitly given function
Function $n(s)$ is given implicitly as $n! = s$. How can I find an asymptotic for $n(s)$? I cannot understand, how can I make an explicit function from this to calculate an asymptotic, as there is no ...
1
vote
1answer
124 views
Asymptotic for binomial coefficient with square root
I'm looking for asymptotic estimate for the binomial coefficient:
$$
\ln{\binom{n}{[\sqrt{n}]}}
$$
I assume Stirling's approximation can help, but I'm not sure I will get any good estimation with this ...
1
vote
0answers
71 views
Master Theorem when B is a fraction.
So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball
$T(n) = 4T(3n/4) + n^4$
Now I used my usual steps of listing out what A, B, ...
0
votes
2answers
357 views
proof that a function plus a lower growth function is theta the first function.
my assignment is to (dis)prove the following
f(n)+o(f(n))=Θ(f(n))
for example:
for all n >= n', n + log(n) = c*n
so ...
1
vote
1answer
146 views
How to prove that a function f(n) exists/belongs to bigTheta?
So as per the title, I'm trying to prove that a function $f(n) = n^2 + 8n$ exists in $\Theta (n^2)$. What I'm having trouble with is the logic/concept behind doing so.
By definition, it would mean ...
0
votes
0answers
40 views
understanding of 1-unconditionality
Let $X=(X, \|\cdot\|_X)$ be normed space with $x_1, \ldots, x_m\in X$.
Assume, $\int_{[-1,1]^m}\|\sum_{i=1}^ma_ix_i\|_Xd\mu(a)=1$, where $\mu$ is the Lebesgue measure on $[-1,1]^m$, $a \in [-1,1]^m$.
...
2
votes
0answers
55 views
gamma funtion and estimates-typo or mistake?
In one of the lecture notes I've found that $C_n$
$$
C_n=
\begin{cases}
\frac{n!}{\sqrt 2 \Gamma((n/2+1)}\pi^{-1/42^{-n/2}(n!)^{-1/2}} & n\text{ even}
\\[4mm]
\frac{2(n!)}{(\sqrt2n+1/(\sqrt2 ...
1
vote
1answer
34 views
Hyperbolic sine and landau notation
I have given a function $f$:
$$ f = \begin{pmatrix} \sinh(x_1 x_2) \\ \cosh(x_1 x_2) \end{pmatrix} $$
We have to show that this is possible:
$$ f = \begin{pmatrix} 2x_1 x_2 \\ 1 \end{pmatrix} + ...
0
votes
1answer
95 views
How can Big-O be proved using derivatives?
Say we have: $$f(n) \in O(g(n))$$
By definition we need to show that:
$$0 \le f(n) \le c\cdot g(n) $$
for some $c>0$ and for all $n>n_0$.
This is usually not difficult when rational and ...
3
votes
1answer
243 views
Disproving a big O equation
As a homework assignment I am trying to prove/disprove the next statement:
Let $f(x)=O_a(g(x))$, then $\forall A,B\in\mathbb{R}\rightarrow A\cdot
f(x)=O_a(B \cdot g(x))$
Which I think is wrong ...
2
votes
1answer
73 views
asymptotic limit at the integral
I would like to get an asymptotic limit at the following integral: for $p\ge 2, n \in N$, $t \ge 0$
$$
\int_{0}^{\frac 12 \sqrt{(n+1)!}}\left(1-\frac{t^2}{2^2(n+1)!}\right)^p \mathrm{d} t
$$
I think ...
