2
votes
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
2
votes
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
2
votes
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
2
votes
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
Finding number of ways of flipping a coin until getting HTH while specifically NOT getting HHH (ARML 2024)
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