New answers tagged

1

If you consider the following functions defined for $x\in \mathbb{R}$: $f(x) = \left\{\begin{array}{rl}1 & \text{if }x\in\mathbb{N}\\x&\text{otherwise}\end{array}\right.$ and $g(x) = \left\{\begin{array}{rl}x & \text{if }x\in\mathbb{N}\\1&\text{otherwise}\end{array}\right.$ Then you have: neither $f \in O(g)$, because whatever the constant $...


1

Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\frac{k+h}{2}$ and $b=\frac{k-h}{2}$. Then $h\cdot k=(a-b)(a+b)=a^2-b^2$, so we only need to square two numbers of at most $n$ digits (if $h$ and $k$ have $n$ ...


0

As a counterexample you can take $f(n)=n$ and $g(n)=\sqrt{n}$. You can think that $f(n)=O(n^2)$ means that an upper bound for $f(n)$ is $n^2$ (of course, without considering multiplicative constant), so the fact that both $f$ and $g$ are bounded by $n^2$ does not implies nothing about the relative behavior of $f$ and $g$.


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.


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, …$ ...


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-...


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.


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

Your algorithm goes over all pairs $(\ell,h)$ of indices such that $1 \leq \ell \leq h \leq n$, and for each of them, runs $\Theta(1)$ operations (the rest of the steps are insignificant from an asymptotic point of view). If there are $M$ such pairs, then the best case, worst case, average case complexity are all equal to $\Theta(M)$.


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

Yes, any constant is a polynomial of degree zero.


Top 50 recent answers are included