1
vote
2answers
22 views

Big O notation - proof

Is it true that $O(k(n) + m(n))$ is equal to $O(\max\{k(n), m(n)\})$? In one of papers on computational complexity I've found the following statement: $$O(\log(n) + n(\log S + \log V )) = O(n(\log ...
0
votes
0answers
11 views

Algorithm that adds three numbers in an array that performs in O(n^2) time

Note that this question extends on this previous question. Given an array A, and a value called value. Does there exist three ...
0
votes
2answers
14 views

Designing a fast algorithm which adds three numbers in array

Given an array A, and a value called value. Does there exist three elements in A where their ...
1
vote
2answers
19 views

Help analyzing the time-complexity of my algorithm

So, (this is homework), we are given an array A, and we are asked to create a function where we return True/False if the array contains three elements which sum to a given value. To formalize: ...
1
vote
1answer
14 views

Series expansions and perturbation

My professor said that $ f \left( y_1(x)+ \epsilon y_2(x)+... \right)= f(y_1(x)) +f'(y_1(x))\> (\epsilon y_2(x)+...) + ...$ but I have no idea how the series continues. Has anyone seen this ...
1
vote
2answers
35 views

Proving that: 800 + n log n + 200√ n log n = Θ(n log n)

I am trying to prove that 800 + n log n + 600sqrt(n)*log(n) = Θ(n*log n) (where log is base 2) Basically so far, I've reduced this expression into an ...
1
vote
1answer
34 views

Does $f(2x) \in Θ(f(x))$ always hold?

If $f(x)$ is continuous and increasing positively, does $f(2x) \in Θ(f(x))$? I am convinced that this is false but I am stuck on the proof. $$0 \le c_1 f(x) \le f(2x) \le c_2 f(x)$$ $$0 \le c_1 \le ...
1
vote
2answers
33 views

If f(n) = O(n), does log(f(n)) = O(log n)?

I have been trying to find a counter-example to prove this is false, however I feel that I am going in the wrong direction. f(n) = O(n), does lg(f(n)) = O(lg n) ...
0
votes
1answer
20 views

What is a polynomially bounded function?

I know this question has been answered before, but I didn't understand the answers and my reputation is too low to comment, since I'm new to stack exchange. Polynomially bounded (I'm pretty sure) ...
1
vote
1answer
21 views

How can I construct a specific sigmoid function?

The simple sigmoid function $$f(x)=1/(1+e^{−x})$$ approaches zero as x tends to negative infinity, and approaches $1$ as x tends to positive infinity. But I want to set $1$ and $20$ instead of $0$ and ...
1
vote
1answer
76 views

Is 1/x the “slowest” asymptotically falling off differentiable function?

As a physicist, I tend to think about $\sim 1/x$ as the "slowest" fall-off of a "reasonable" function. Let us state this formally: $${\rm lim}_{x \to \infty} f(x) = 0, f(x) \in Reas \implies \exists A ...
1
vote
1answer
32 views

Lower bound on $F$ under the assumption $\theta F(s)\le sF'(s)$

Let $F(s)=\displaystyle \int_0^{s}f(t)\,\mathrm dt$. We suppose that there exists $\theta>2$ such that $\theta F(s)\le f(s)s$ for all $s\in \mathbb{R}$ and that $F(s)>0$ for all ...
0
votes
2answers
44 views

When $\ln(1+y) = y + o(y)$?

I was reading a proof which utilize the fact that: $\ln(1+y) = y + o(y)$ http://math.stackexchange.com/a/842557/160028 I'm not so sure what is the meaning of $\ln(1+y) = y + o(y)$. When is it ...
6
votes
1answer
99 views

Some conditions to obtain that $\int_1^{x}e^{f(t)}dt\sim_{x \rightarrow +\infty}\frac{\exp(f(x))}{f'(x)}$

Playing with the function $e^{t^2}$ I conjectured the following result : Let $f\in C^2(\Bbb{R},\Bbb{R})$, assume that : $f'(x)\rightarrow_{x \rightarrow +\infty}+\infty$ ...
1
vote
2answers
46 views

Check my proof: Big O notation

I was asked the following: We are given the functions $f(n)=n^{10\log(n)}$ and $g(n)=(\log (n))^n$. Which of the following statements is true: $f(n)\in\mathcal{O}(g(n))$, $f(n) \in ...
-3
votes
2answers
99 views

A function that increases faster than $\ln(x)$ when $x$ is small and then slower than $\ln(x)$ when $x$ is big.

As the title indicate: I am looking for a function that increases faster than $\ln(x)$ when $x$ is small and then slower than $\ln(x)$ when $x$ is big. Here is the fig: The red curve is the ...
-1
votes
0answers
22 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
1
vote
1answer
12 views

relation between $|o(f)-g|$ and $|f-g|$

This question is similar to the one asked some hours ago. I have given three functions $f,g,h$ where $h(n)=o(f(n))$ and I know that $|f-g|<d<1$. Now I'd like to find an Expression for $|h-g|$. ...
0
votes
1answer
20 views

$O(f)-g = O(f-g)$: asymptotics of difference of functions

I have given three functions $f$, $g$, $h$ where it might be relevant that all these functions are bounded from above by $1$. I know that $$|f-g|=d$$ where $d$ may depend on $n$ and I know that ...
0
votes
1answer
70 views

f(n)=theta(f(n/2)). Prove or disprove

I am trying to prove that the statement f(n)=theta(f(n/2)) is true. This is what I have so far. I am not sure it is correct. Assume f(n)=Theta(f(n/2)). Then f(n)=O(f(n/2)) and f(n)=Omega(f(n/2)). ...
-1
votes
2answers
63 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not? [closed]

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? i know x^2+25x+4≤25x^2+25x+25≤25x^2+25x^2+25x^2=75x2 for some x what confuses me is x^2+25x+4≤25x^3+25x+25≤25x^3+25x^3+25x^3=75x3 ...
1
vote
2answers
55 views

Trouble understanding Big O notation for a sum of n integers [duplicate]

This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers? Solution: Because each of the integers in the sum of the ...
1
vote
2answers
55 views

Describing asymptotic behaviour of a function

For question B! x^2+x+1/x^2 = 1+ [x+1/x^2] shouldnt the answer be asymptote at x=0 and y=1 ?? i dont understand the textbook solution
3
votes
2answers
33 views

Existence of $f_n(t)=o(f(t))$ where $(f_n)$ is a sequence of functions.

Let $(f_n)$ a sequence of functions over $\mathbb{R}$ to $\mathbb{R}$, Show that there exist $f:\mathbb{R} \rightarrow \mathbb{R}$ such that $f_n(t)=o(f(t))$ I suspect that $f_n$ converges ...
2
votes
2answers
51 views

interpreting limits

a short question: is this true that if: f(x) = $2^x$ g(x) = $100^\sqrt{x}$ $\lim\limits_{x \to \infty} \dfrac{f(x)}{g(x)}$ = $\infty$ then for x sufficiently large f(x) is always greater than ...
1
vote
1answer
30 views

Construct two functions based on big O constraint

I'm doing an algorithm problem goes like this. Construct two functions $f$, $g$ : $\mathbb{R}^+\rightarrow\mathbb{R}^+$ satisfying, $f$, $g$ are continuous; $f$, $g$ are monotonically increasing; ...
1
vote
1answer
147 views

A question about prime gaps

Recently, I have been reading the Wikipedia article about prime gaps (http://en.wikipedia.org/wiki/Prime_gap) and I came across the following: Hoheisel was the first to show that there exists a ...
2
votes
1answer
43 views

Are there functions so that $f(n) \notin \mathcal{O}(g(n))$ and $g(n) \notin \mathcal{O}(f(n))$?

Note that the functions should be $\mathbb{N}_0 \rightarrow \mathbb{N}_0$. So I was thinking about something like $$f(x) = 1 + \sin(\frac{\pi x}{2})$$ $$g(x) = 1 + \cos(\frac{\pi x}{2})$$ which ...
2
votes
1answer
52 views

Show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$

Another question about asymptotic approximations. We are asked to show that $\operatorname{ln}(n!)=\Theta(n\operatorname{ln}(n))$ I'm stuck tho and can use help. What I did is: ...
0
votes
0answers
34 views

check my short simple proof - Functions are of same magnitude. Asymptotic notation.

A simple question with a short solution I thought of, but I would like verification. $f(n)$ is a function that approaches infinity as $n$ approaches infinity. We are asked to show that ...
0
votes
2answers
60 views

If $f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or any other one-line relation?

$f(x)=O(g(x))$ & $g(x)=O(f(x))$ then can we write $f(x)\sim g(x)$ or $$\lim_{x \to \infty}[f(x)/g(x)]=1$$ where f(x)=pi(x)(prime counting function) and g(x)=li(x)(logarithmic ...
0
votes
1answer
43 views

Does $ \log(x)^{x^a}$ eventually dominate $x^k$?

Does $ \log(x)^{x^a}$ eventually dominate $x^k$ for all $a\gt 0$ and for all positive integers $k$? And if so, how does one prove this? Thanks a lot for your help.
0
votes
1answer
105 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
1answer
176 views

Does log $f(n) = O($log $g(n))$ imply $f(n) = O(g(n))?$

Assuming log is base 2, if I know that: log $f(n) = O($log $g(n))$. Does this imply that $f(n) = O(g(n))$? I understand that the converse is true.
2
votes
1answer
54 views

Comparing time complexities

I'm trying to understand which of the following functions is strictly faster growing ($\Omega$, $o$-notation or $\theta$-notation). Not sure how to approach the following equations: $$\bf{n^{0.3} \ ...
1
vote
2answers
608 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
58 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
2
votes
3answers
88 views

Need an asymptotic function that's going to have a specific shape

I'm looking for a function y = f(x) that grows quickly at first, and slowly later, asymptotically approaching 100. I need it to hit certain specific points... What I need is: ...
1
vote
1answer
68 views

Does $f'(x) \in o(g'(x))$ imply $f(x) \in o(g(x))$ for monotonically increasing $f$ and $g$?

The title says it all. This seems intuitively true to me, but I'm not sure how one would go about proving this. (I'm asking because I'm trying to show that $x^n \in o(x^{n+1})$ for all natural $n$, ...
0
votes
1answer
48 views

question about functions (asymptotic)

This is right? $f=\Omega(g)\Rightarrow2^f=\Omega(2^g)$? If not I'd like to get a Counter-example. Thank you!
4
votes
1answer
101 views

Iterated function?

$$f(n) = \frac{n}{\lg n}$$ $$g(n) = \min (i \ge 0: f^i(n)\le 2)$$ In other words, $g(n)$ is the number of times $f(n)$ needs to be iterated to reduce $n$ to 2 or less. What's a tight bound on ...
1
vote
1answer
54 views

How do we determine as to how long we should sum an asymptotic series of a function to get the answer correct up to a particular precision?

As an example, consider the asymptotic expansion for polygamma function . What should be the min value of 'k' in the equation to get the answer correct upto a particular precision, say pth. Is there ...
2
votes
0answers
99 views

Upper bound for linear function

What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$. $$an + b ...
0
votes
0answers
26 views

I don't understand how the sign of argument works in a function with arguments that could be positive, negative or in between

this formula is from http://en.wikipedia.org/wiki/Airy_function i want to know what is the value of Ai(large negative number) but if z is negative the formula below gives minusxminus = positive ...
1
vote
2answers
44 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.
0
votes
1answer
2k 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 ...
0
votes
1answer
56 views

asymptotic expansion, interpretation

I am interested in asymptotic behavior of a function at infinity: $$ f(r)=\frac{0.04962 e^{-2 r} (r-1.000)}{\left(\left(e^{-2 r}\right)^{2/3}+0.06119\right)^2 r} $$ Tried ...
3
votes
2answers
30 views

Simple question about asymptotics of a ratio

What is the largest exponent $\alpha$ such that the ratio between $ n^{\alpha}$ and $ (\sqrt{n} / \log{ \sqrt n}) $ still remains asymptotically bounded (can assume $n$ positive integer) ?
3
votes
1answer
264 views

Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?

For example, suppose I wanted to determine which of the following has the fastest asymptotic growth: $n^2\log(n)+(\log(n))^2$ $n^2+\log(2^n)+1$ $(n+1)^3+(n-1)^3$ $(n+\log(n))^22^{100}$ Are there ...
2
votes
2answers
50 views

Study of a series of functions

I've to study this series: $$\sum_{n=1}^\infty e^{\sqrt n\,x}$$ My teacher wrote that with the asymptotic comparison with this series: $$\sum_{n=1}^\infty\frac{1}{n^2}$$ My series converges ...