I was searching the algorithm for finding the composition of 2 linear functions n times (where n can be as large as 10^18) in O(log n) time. I just got a pdf ( http://ift.tt/1JfjeLV ) containing polynomial composition of 2 functions with large degrees using divide and conquer algorithm.
I was wondering whether my problem for composition of linear function n times can also be solved using divide and conquer algorithm in O(log n) complexity?
If yes, please explain the algorithm.
Thanks, in advance.
EDIT 1: The composition of function f(x) n times is fofof...n-times. Here the function is to be composed to itself n times. There are no 2 functions.