7

Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$, hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is asymptotically as hard as multiplying.


6

Let's take accordingly $f=2^{-\sqrt n}\varepsilon_1$ and $g=2^{-\frac{n}{2}}\varepsilon_2$, where $\varepsilon_1,\varepsilon_2$ tends to zero. Then you would like to have $f + g - fg = 2^{-\sqrt n} \varepsilon$. So, for $\varepsilon $ we have: $$\varepsilon = 2^{\sqrt n}\cdot\big(2^{-\sqrt n}\varepsilon_1 + 2^{-\frac{n}{2}}\varepsilon_2 - 2^{-\sqrt n-\frac{...


3

You could use "guess-and-check": guess the solution to the recurrence, then use induction to prove that it is a solution, i.e., to prove that your solution satisfies the recurrence. In your case, since you know Akra-Bazzi, your "guess" can actually be obtained through Akra-Bazzi, but you don't have to tell anyone that's how you obtained ...


3

I may be wrong, but it seems to me that the function defined by: $f(n) = \left\{\begin{array}{rl}1 & \text{if }n=1\\2^{2^{\left\lfloor \log_2\log_2 n \right\rfloor+1}}&\text{otherwise}\end{array}\right.$ satisfy the conditions. To explain why, the values taken by $f(n)$ will be $1, 4, 4, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 256, 256, …$ ...


3

$O(n)$ is the set of all functions $f(n)$ such that, for sufficiently large $n$ and a positive constant $c$, $f(n) \le cn$. $1+\Theta(\frac{1}{n})$ is an abuse of notation that denotes the set of all functions $h(n) = 1+g(n)$ such that, for sufficiently large $n$ and a two positive constants $c_1$, $c_2$, $\frac{c_1}{n} \le g(n) \le \frac{c_2}{n}$. Then the ...


2

Let $n_0 = n$ and $n_{i+1} = n_i - \log n_i$. Then $T(n)$ is one plust the minimal $t$ such that $n_t \leq 1$. Clearly $n_{i+1} \geq n_i - \log n$, hence $n_t \geq n - t\log n$, implying that $T(n) \gtrsim n/\log n$. In the other direction, as long as $n_i \geq \sqrt{n}$, the sequence decreases by at least $\tfrac{1}{2} \log n$, hence it takes at most $2n/\...


2

Yes, any constant is a polynomial of degree zero.


2

If you are just interested in an upper bound you can notice that $T(n) \le S(n)$ where $S(n) = 3 S(n/3) + \frac{n}{2}$ and has solution $S(n) = O(n \log n)$. Alternatively there is always induction. You can show that, for $n \ge 2$, $T(n) \le c n \log n$. For $2 \le n < 7$, $T(n)$ is a constant and $n \log n \ge 1$. Therefore the claim is true for a ...


2

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed. The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the ...


2

You can use the Akra-Bazzi theorem as $$g(x) = n^3 \in O(n^c), a_1=2, a_2 = 1, b_1 = \frac{1}{3}, b_2 = \frac{2}{3}$$ So, just we need to find $p$ such that: $$2\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$$ You can find the computation for finding $p$ here. It is around $1.4$. Now, we can write: $$T(n) \in \Theta\left(n^{p}\left(1 +‌ \int_{1}^...


1

In general, it is not: see Summation of asymptotic notation, Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?. But if each $O(f(k))$ term uses the same hidden constant, then it follows by expanding the sum: see https://en.wikipedia.org/wiki/Big_O_notation#Sum, Summing big-O-notation, and then apply them repeatedly.


1

There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees. Your recursive procedure actually computes two different functions: the first output is a Boolean function $b$ which measures whether the tree is balanced, and the second is an integer-...


1

Akra and Bazzi proved a generalization of the master theorem which, in particular, implies that the formulas in the master theorem remain true even if you're adding some "noise" of the form you consider. In fact, the Akra–Bazzi theorem can handle noise of magnitude $O\bigl(\frac{n}{\log^2 n}\bigr)$.


1

The basic way to understand notation like $f(n) = O(g(n))$ is that the equals sign is really wrong, it should be something like $f(n) \in O(g(n))$, the function $f$ belongs to a set of functions. That set is the set of functions $h$ such that for some constants $c > 0$ and $n_0$ it is $h(n) \le c g(n)$ whenever $n \ge n_0$ (this presumes non-negative ...


1

Let us try to prove that $T(n) \geq cn^p$ by induction. For small enough $c>0$, this would hold for the base case. For the inductive step, $$ T(n) = T(n/3) + T(n/6) + 1 \geq c(n/3)^p + c(n/6)^p + 1 > cn^p. $$ Unfortunately, the same approach doesn't work directly for the upper bound. Instead, we will prove that $T(n) \leq Cn^p - 1$ by induction. For ...


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