I'm reading a book called "From Mathematics to Generic Programming" by Alexander A. Stepanov and Daniel E. Rose, the second chapter contains a description of Egyptian Multiplication algorithm. Its complexity described as # (n) = [log n] (ν(n) - 1). In general it's totally understandable but what does "# " means? Is it a form of notation for a mathematic function or something?

CodePudding user response：

'#' often denotes "the number of", and the ' ' sign is used as an index. So we have "the number of additions".

CodePudding user response：

In that book before giving the equation, the author says,

How many additions is multiply1 going to do?
Every time we call the function, we’ll need to do the addition indicated by the in a   a.
Since we are halving the value as we recurse, we’ll invoke the function log n times. And some of the time, we’ll need to do another addition indicated by the in result   a.
So the total number of additions will be # (n) = ⌊log n⌋ (ν(n) − 1)

int multiply1(int n, int a) {
    if (n == 1) return a;
    int result = multiply1(half(n), a   a);
    if (odd(n)) result = result   a;
    return result;
}
bool odd(int n) { return n & 0x1; }
int half(int n) { return n >> 1; }