0
$\begingroup$

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf

enter image description here

From my understanding and this thread, https://math.stackexchange.com/a/928412, we need 3 steps for that proof. The first case is trivial and true. Now we have assumed the same for i and going to prove that it is true for i+1. I'm unable to clearly see how they have made that deduction in this answer.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are you asking why $O( (p^i(n))^k ) = O(p^{i+1}(n))$? $\endgroup$
    – Dima Chubarov
    Commented Jul 20, 2016 at 2:30
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Commented Jul 20, 2016 at 6:51
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$
    – Raphael
    Commented Jul 20, 2016 at 6:51
  • 2
    $\begingroup$ What specifically do you not understand? $\endgroup$
    – Raphael
    Commented Jul 20, 2016 at 6:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.