How to prove that one problem belongs to class P? Is there any typical proving method when proving that one problem belongs to class P?
For example, when proving that
The problem of finding n to the kth power is the P problem. (Each multiplication can be done in unit time)
If you present an algorithm that can solve this problem with $O (\log n)$, can it be a proof?
Yes. In fact, any algorithm that runs in polynomial time counts. For examle, even an $O(n^8)$ would suffice! Therefore, there is no real need to optimize your algorithms to such extremes.