Skip to main content
added 8 characters in body
Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

The integral is in $\Theta(\frac{n^{2-p}}{\log n})$, and, substituing it back in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align*} \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align*} $$

The integral is in $\Theta(\frac{n^{2-p}}{\log n})$, and substituing in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align*} \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align*} $$

The integral is in $\Theta(\frac{n^{2-p}}{\log n})$ and, substituing it back in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align*} \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align*} $$

Source Link
Steven
  • 29.6k
  • 2
  • 28
  • 49

The integral is in $\Theta(\frac{n^{2-p}}{\log n})$, and substituing in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align*} \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align*} $$