# Tagged Questions

22 views

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) ...
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) ...
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 ...
76 views

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 ...
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 ...
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: ...
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$, ...
48 views

This is right? $f=\Omega(g)\Rightarrow2^f=\Omega(2^g)$? If not I'd like to get a Counter-example. Thank you!
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 ...