I have seen in many other videos on YouTube, also in this lecture by checking out his constraint on n constraint bhaiya defined that we need to this problem in O(k^3 logN) time.
I’ve faced this problem with CodeChef also. These constraints give a headache, please give some insights on it.
How time complexity of algo is determined?
@dev.divyanshu19 time complexity of matrix exponentiation is
where matrix’s dimensions are (k,k) and power raised is N.
this is because multiplying two matrices has k^3 cost, also we multiply logN times.
Hence overall complexity becomes O(k^3logN ).
I’m not asking specifically about this problem, I’m asking about general guessing of time complexity using the given constraints in the problem.
see usually an online judge can perform about 10^8 iterations per second.
So with given constraints and knowing the complexity of algorithms, you may know which algorithm will work.
For example in this case, k=100 and n=10^18 is maximum you can do!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.