-3
votes
2answers
86 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 ...
0
votes
0answers
21 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
19 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
30 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)). ...
0
votes
2answers
61 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
40 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
49 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
28 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
141 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
40 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
33 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
59 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
79 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
152 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
53 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
501 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
52 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
81 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
47 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
91 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
53 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
90 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
43 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
243 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 ...
0
votes
1answer
227 views

On determining if a function is eventually non-decreasing

I've just had an idea or intuition, but I couldn't be sure if it is correct or not: Let's say I have a function $f(n)$ such that it can be expressed as $\frac{g(n)}{h(n)}$ where $g(n)$ and $h(n)$ are ...
1
vote
1answer
190 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 ...
2
votes
3answers
330 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
3
votes
1answer
299 views

All asymptotes of $f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$

Find the number of all possible asymptotes of: $$f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$$ Since we know $\sqrt{ax^2+bx+c}\approxeq \sqrt{a}\big|x+\frac{b}{2a}\big|$ when $(x\rightarrow\pm\infty)$ so, ...
0
votes
1answer
279 views

Asymptotic notation - some equations.

i have a problem with proof one of this facts: $2^{2^n}$ = $\Theta (n^n)$ or $2^{2^n}$ = $O (n^n)$ or $2^{2^n}$ = $\Omega (n^n)$ and to proof one of this: $(n^n)$ = $\Theta (2^{2^n})$ $(n^n)$ = ...
2
votes
3answers
228 views

Intermediate growth rates

Is there any simple function/formula $f(n)$, which eventually dominates every $cn$ for every $c$, and is eventually dominated by $a \cdot n \cdot \ln^k(n)$ for every $a,k \in \mathbb{Z}$, where ...
0
votes
1answer
972 views

Compare growth rate of functions

I was given homework to sort some (14) functions in order of their growth rate. I am confused about two functions $3^\sqrt{\log n}$ and $n^{\log n}$: about where these two lie within those 14 ...
0
votes
2answers
111 views

Finding $\Omega(f(n))$

Is there a standard way to find a $\Omega$ of a function $f(n)$ ? I mean, I'm trying to understand how to determine: $$g(n)=\Omega(f(n))$$ where $f(n)$ is a polynomial or logarithmic function I ...
4
votes
3answers
6k views

Family of functions with two horizontal asymptotes

I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch): Properties I'm looking for: ...