Time complexity of matrix exponentiation

#1

The time complexity will be kˆ3 * log2N + kˆ3 right ? (which I understand is kˆ3*log2N in asymptotic notation.) Am i right or not in this calculation?.

#2

Would you please tell how have you calculated this?

1 Like
#3

Sorry the que was not clear. I was talking about the complexity of Calculating Fn using T^n-1 * F1 . The extra k^3 part due to multiplication of the resultant tranformation matrix (kk) with F1 (k1) matrix.

#4

For knowing complexities of recursive functions, you shall study Master theoram else you may get wrong