3

Let's redo your calculation. You want $$ \log^kn \geq C \sqrt{n} $$ to hold for some $C>0$ and large $n$. Taking the logarithm, $$ k \log \log n \geq \log C + \tfrac{1}{2}\log n, $$ and so $$ k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n} $$ should hold for large $n$. In other words, $$ k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log ...


2

Nicest version of the Akra-Bazzi theorem I've seen is the one in Lehman, Leighton, Meyer "Mathematics for Computer Science", the discussion starts at page 1019. An (older) print version is available. No proof, though. Would need to slough through Leighton's note to verify that the lecture notes/book version is right (it has somewhat different conditions, ...


2

In my opinion the problem statement seems poorly posed. It's not clear what is meant by the problem statement. Normally, if we write $a$ or $b$ the assumption is that they are a constant: they do not depend on $n$. If they are intended to be a function of $n$, then they should be written as $a(n)$ or $b(n)$. Since that wasn't done, the only assumption I ...


2

Assume $n>1$. The solution to $k^k=n$ is $k=e^{W(\log n)}$, where $W(\cdot)$ is the Lambert W function. Another way to express the solution is $$k = \dfrac{\log n}{\log\dfrac{\log n}{\log\dfrac{\log n}{\log\dfrac{\log n}{\cdots}}}}.$$ In other words, $k$ is the limit of $k_0=\log n$, $k_1=\dfrac{\log n}{\log k_1}$, $\cdots$, $k_{t+1}=\dfrac{\log n}{\...


1

$c=\frac{1}{2}$ is enough for large enough $n$. Indeed, there are positive integers $n_1$ and $n_2$ such that $$\begin{eqnarray*} n &\ge& n_1 \implies -\frac{1}{2} < \log_2 \left ( 1 - \frac{1}{n} \right ) \\ n &\ge& n_2 \implies -\frac{1}{2} < -\frac{1}{n} \log_2 (n - 1). \end{eqnarray*}$$ Rewriting $$cn \log_2 \left ( 1 - \frac{1}{...


1

Apply the definition. Does there exists $\epsilon>0$ such that $f(n) = O(n^{1-\epsilon})$? If yes, then case 1 applies (just see the text that you included in the question). If no, then case 1 does not apply. For instance, ask yourself: if $\epsilon=0.1$, does $f(n)=O(n^{1-\epsilon})$? i.e., does $\log n=O(n^9)$? You should be able to take it from ...


1

We have: $$\log_2(2n) = \log_2(2) + \log_2(n) = 1 + \log_2(n) < 2 \times \log_2(n)$$ You can take $c = 2$ and as $\log_2(2n) < c \times \log_2(n)$ for $n > 2$, we can say $\log_2(2n) \in O(\log_2(n))$.


1

$(n^2)!$ is the product of the numbers 1 to $n^2$. $(n!)^2$ is the product of the numbers 1 to n, multiplied by the product of the numbers 1 to n again. In the first product, we have $n^2 - n$ numbers ≥ n plus some others. In the second product we have 2n numbers ≤ n. So if we take the logarithm, the first is ≥ $(n^2 - n) log n$, the second is ≤ $2n log n$...


1

This is a quadratic function; therefore $f$ is big-Theta of $n^2$. Therefore, it is both Big-O and Big-Omega of $n^2$. However, when a function $f$ is big-Omega of another function $g$, then $f$'s growth is of greater or equal order than $g$. However, since a quadratic grows strictly faster than a linear in the long run, $n^2$ is big-Omega of $n$. Think of ...


1

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.


Only top voted, non community-wiki answers of a minimum length are eligible