New answers tagged binary
0
Well, first of all, i_right = i_left + 1. Always. It's obvious, so bellow I'm gonna show only proof of expression i_left_child = i_parent * 2 + 1.
In the explanation bellow there might be quite many definitions like: parent, child, index, position in current level, etc. So instead of greek/latin letters I decided to use the exact numbers from picture, but ...
0
It's a recursive algorithm. Each time you call mul (through the use of p) you decrease the number of bits of 'a' by one. So the time complexity is the number of bit in 'a'. And since the number of bits equals the log of the value of 'a', so the recursion depth is Log(a).
In each step of the recursion you might perform an add operation of Max(Log(b),Log(a)) ...
Top 50 recent answers are included