New answers tagged efficiency
2
Let $\sigma(S)$ denote the sum of all the elements in $S$ and $A_i = \{a_1, \dots, a_i\}$.
Given, $i=0,\dots,n$ and $w \in \mathbb{Z}$,
define $OPT[i,w]$ as the mazimum cardinality of a subset $S \cup S' \subseteq A_i$ where $S \cap S' = \emptyset$
and $\sigma(S) - 2\sigma(S') = w$.
If no possible choice for $S$ and $S'$ exists, then let $OPT[i,w]=-\infty$....
1
What you want to prove is false.
$T(n) = 16 T(n/4) + n^2\log^3 n$ has solution $T(n) = \Theta(n^2 \log^4 n)$.
To see this notice that this recurrence fits in the general form $T(n) = a T(n/b) + f(n)$ once you set $a=16, b=4, f(n)=n^2\log^3 n$.
Since $f(n) = n^2 \log^3 n = \Theta( n^{ \log_b a } \cdot \log^k n)$ for $k=3$, you can apply the Master theorem ...
-1
Perhaps this is a reference to Cobham's thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis?wprov=sfla1. Usually the word used is "feasible" though.
3
There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts.
In general, if you think your audience might not be sure about ...
Top 50 recent answers are included
