New answers tagged

-1 votes

Runtime complexity of permutation function

Consider this piece of code: for i in range(len(nums)): dfs(nums[:i]+nums[i+1:], curr+[nums[i]], res) Note that ...
user avatar
  • 791
1 vote

How are regular languages not structurally recursive?

Regular languages don't have recursive structures, so formally regular expressions cannot express recursive structures by definition.All regular languages can be recognized by a finite automaton. A ...
user avatar
1 vote

Compute a commutative and associative operation on n-2 arguments efficiently

(Motivation: let $h = n/2$. Given $f_{ih} = f(x_i\dots x_{h-1}) \text{ and } f_{hj} = f(x_h\dots x_j)$ (precomputed in about $n$ evaluations of $f$), $f(x_{i+1}\dots x_{j-1})$ can be computed as $f(f_{...
2 votes
Accepted

Compute a commutative and associative operation on n-2 arguments efficiently

(1) You can compute $f(x_1,\dots,x_{i-1})$ for all $i$ with $n-2$ calls to $f$. (Simply iterate over $i:=1,\dots,n$.) (2) Then, using (1), you can compute $f(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{j-1})$ ...
user avatar
  • 141k
0 votes

Compute a commutative and associative operation on n-2 arguments efficiently

Count how many times each $x_i$ occurs in the argument list. Suppose $X_1$ is the set of $x_i$ that occur once, $X_2$ is the set of $x_i$ that occur twice, ..., $X_m$ is the set of $x_i$ that occur $m$...
user avatar
  • 115
0 votes

Complexity of T(n)=2T(n-1)

A sum of $m$ constants takes time $O(m)$.
user avatar
  • 3,911
1 vote

Show that the function that counts the number of occurrences of 6 in a natural number is recursive primitive

Here is a recursive function for your problem: \begin{align*} & \mathrm{count6}(n) = \mathrm{cond}(\mathrm{eq}(n, 0), 0,\\ & \quad \mathrm{add}(\\ & \quad \quad \mathrm{cond}(\mathrm{eq}(\...
user avatar

Top 50 recent answers are included