All Questions
Tagged with logarithms asymptotics
309
questions
1
vote
0
answers
67
views
What does "any polynomial dominates any logarithm" mean here?
My textbook states that
any polynomial dominates any logarithm: $n$ dominates $(\log n)^3$. This also means, for example, that $n^2$ dominates $n\log n$
However, it wasn't clear to me what the ...
- 3,019
0
votes
1
answer
46
views
Determining the witnesses (constants $C_0$ and $k_0$) when showing $(log_b n)^c$ is $O(n^d)$ (b > 1 and c,d are positive)
I'm having a hard time finding the constants/witnesses $C_0$ and $k_0$ that show $(\log_b n)^c$ is $O(n^d)$. That is $|(\log_b n)^c| \leq C_0|n^d|$ for $n > k_0$ (b > 1, and c,d are positive).
I ...
- 883
1
vote
2
answers
59
views
Unexpected asymptotic logarithm behavior
I have recently seen a rather confusing asymptotic property of logarithms:
$$
\log(n^4 + n^3 + n^2) \leq O(\log(n^3 + n^2 + n))
$$
I find this very unintuitive. Why would the log of a bigger ...
1
vote
2
answers
71
views
How to deal with asymptotics of $\log(1-x)$ when $x$ is approaching $1$?
Consider $$\log(1-x)$$ where $x=x(n)\rightarrow 1$ when $n\rightarrow \infty$.
What is the asymptotics of this function?
Related question
- 1,052
0
votes
2
answers
49
views
How to deal with asymptotics of $\log(1+x)$ where $x$ doesn't belong to $(-1,1)$?
Consider
$$\log(c_1+c_2 \frac{1}{p(n)-2})$$ where $p(n)$ is decreasing function approaching $2$, and $c_1,c_2$ are constants that do not depend on $n$.
Question What is the asymptotics of this ...
- 1,052
-1
votes
1
answer
124
views
Approximating $(\log n)^n$ using Big O notation
As stated in the title I am trying to find a good approximation in O notation for:
$$(\log n)^n = \log (n) \cdot \log (n) \cdot ... \cdot \log (n)$$.
I have tried using L'Hôpital's rule for the term
$...
- 1
0
votes
0
answers
83
views
How to reduce a $(\log_2n)^2$
I am given 5 algorithms and the steps they took like $O(n^2)$, $o(n^2)$, $Ω(n^2)$, $Ω(n)$
I am asked to associate certain equations with the above and one of these is:
$$(\log_2 n)^2+75$$
And
$$7n!$$
...
- 3
1
vote
2
answers
70
views
Asympototic estimation of log log function
Let $N>0$ be an integer and consider the sum $\sum_{n=3}^N(\log \log N-\log \log n)$. It is not hard to see that this sum has the complexity $O(N^2)$ since $\log \log x <\log x<x$, so that ...
- 488
0
votes
3
answers
114
views
Big-Oh notation question
When we have a question like so:
What is the smallest integer $n$, such that $f(x) = x^{5.7}(\log x)^{1.2}$ is $O(x^n)$?
Would we go about the question as so: round up $x^{5.7}$ to become $x^6$.
Since ...
8
votes
1
answer
203
views
How to approximate the median of the numbers in the first $n$ rows of Pascal's triangle?
How can we approximate the median of the numbers in the first $n$ rows of Pascal's triangle? (The top row is the $0$th row.)
Using Excel, I made a graph of the natural log of the median against $n$, ...
- 25.7k
2
votes
0
answers
69
views
Show that $ \lim_{x \to -\infty} (1 + \sum_{n=1}^{\infty} (\frac{x}{\ln^2(n+1)})^n ) = 0$
Let $x$ be real and define the entire function $f(x)$ as
$$ f(x) = 1 + \sum_{n=1}^{\infty} (\frac{x}{\ln^2(n+1)})^n $$
Now we have that
$$ \lim_{x \to -\infty} f(x) = \lim_{x \to -\infty} (1 + \sum_{...
- 16.4k
1
vote
1
answer
63
views
Why is $\log(\log^*(n)) = Ω(\log^*\log(n))$ is true while $\log^*\log n$ is bigger than $\log \log^*n$?
In field of algorithm and data structure I came across this problem.
As far as I know
$$\lg^* \lg n > \lg \lg^* n$$
is true in term of growth rate
and also noticed that
$$\log(\log^*(n)) = Ω(\log^*\...
- 21
7
votes
3
answers
644
views
Different logarithm basis equivalence in big-O notation
Often, when I encounter big-O notation during computations, the basis of the logarithm is omitted. Is there an error, or is it in some sense irrelevant? Or am I missing something?
For instance, $\...
- 75
0
votes
2
answers
59
views
$g(n)$ upperbounds $f(n)$ but graph shows otherwise
Given we have the following functions:
$$f(n)=\log_{2}^{4}n$$
$$g(n)=2^{\sqrt{\log_{2}n}}$$
I've done the limit of f(n) over g(n), and found that g(n) is an upperbound of f(n) given the zero result:
$$...
0
votes
0
answers
34
views
$O(\ln(\ln n))$ rounds to achieve $(\ln n)^4$ players
I'm reading a paper on Randomized Rumor Spreading and I'm confused about part 2.1. startup phase (page 4).
We try to spread a message ("rumor") using a push-scheme, where each informed ...
- 37