# Tag Info

Accepted

### What is a closed-form expression for the number of matrix multiplications in this repeated squaring algorithm?

Slight modifications are made below to make it $O(\log n)$: \begin{array}{l} \texttt{def matrix_exp($X,n$):} \\ \texttt{if $n=0$ return $I$} \\ \texttt{if $n=1$ return $X$} \\ \texttt{if $n$ is even [ ...
• 1,875

### What is a closed-form expression for the number of matrix multiplications in this repeated squaring algorithm?

For $n \geq 1$ it requires $n-1$ multiplications, and of course for $n=0$ it requires 0. This can be proven by strong induction. Base case: Note that for $n=1$ by the special case there are no matrix ...
• 2,636

### How many permutations of [26] have exactly 24 cycles?

As suggested by the comment, this is a case that can be done by inspection. The number of trivial cycles (fixed points) can obviously not be larger than or equal to $24$. It can also not be smaller ...
• 10k

### Using primitive recursion for defining a function of one argument

There are different conventions, sometimes the case $k = 1$ is treated with a separate definition where $f(0) = c$ for some constant, and sometimes we indeed consider functions with $k = 0$ (nullary ...
• 2,699
1 vote
Accepted

Think about what state the game is in at any moment, labeling the states by how much of a potential winner (for either side) you have running. Thus the states can be thought of as $START, H, HH, HT, ... • 72.5k 1 vote ### Formalizing a Recursion for Expectation Personally I would say take "to see$n+1$sixes we need to first see$n$sixes and then we need another six" as saying you take an expected$E_n$rolls from the start to get$n\$ consecutive ...
• 160k

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