Book Corrections - Complexity Notation & Euclidean Algorithm

[Uabanur]

While reading through the leading chapters of the book on https://www.algorithm-archive.org/ (august 10'th, 2018) I found some sections/descriptions which felt incomplete, and thought I might give my feedback.

Complexity Notation:

• It is unclear what is seen as an operation. It assumed that the operation initially is seen as the array-lookup, and not the print statement.

• In example two the operations are conditional to the length of the array which is unnecessary for the point of the example.

• In the second example of 'Linear Time', the explicit runtime is said to be Theta(3n/2+2) but again it is ambiguous as to what counts as an operation. If it is focused on array-lookup as well as the addition operation, the time would instead be Theta(5n/2+2), assuming we ignore the println statement of the independent string. To further state this argument, the multiplication and addition of the array index would also be calculated separately before the array-lookup, as well as printing the independent string, making the explicit runtime Theta(10n/2+3).

• The chapter nicely grasps the concept of complexity notation, but does not describe how O and Omega are the upper and lower bound of Theta very well. This could be clear with an example also.

• The exponential example has no terminating condition, causing stackoverflow independent of parameters.

• The logarithmic example is not logarithmic, as both branches are explored.

Euclidean Algorithm:

• the euclid_mod and euclid_sub examples are swapped in the text.

[Gathros]

The Euclidean Algorithm problem has been solved, in #366, thanks.

[dovisutu]

Well... For the logarithmic algorithm in book, if you run it on a parallel computer, it might be logarithmic if the 2 branches of this algorithm are parallel running. But if you run it on a serial computer, this never work -- it'll just take O(n) to run. Maybe we can use binary search:

template <typename Iter, typename T>
Iter binary_search(Iter first, Iter last, T target) {//searching in an ascending ordered vector
    Iter middle = first;
    middle += (last - first) / 2;
    if (target == *middle) return middle;
    if (target > *middle) return binary_search(middle + (last - middle) / 2, last, target);
    else return binary_search(first, middle - (middle - first) / 2, target);
}

But problem is this should belongs to Sorting and Searching Chapter. Maybe waiting for a better idea?

[dovisutu]

I think the better way to realize logarithmic algorithm by "array outputing" is the following:

template <typename Iter>
void logarithmic_algorithm(Iter first, Iter last) {
    std::cout << *(first + (last - first) / 2) << endl;
    if(last - first == 0) logarithmic_algorithm(first, first + (last - first) / 2);
}

but it's in c++, and I don't know Julia so much. Well, maybe I'll create a branch for it.