Time complexity of Maximum independent Set Algorithm

447 views Asked by At

I am learning how to find out the time complexity of the Maximum Independent Set problem using branch and reduce method. The following is the calculation copied from the textbook.

Here I am unable to find out how the red box marked line came from it's previous line.In the previous line also, why is the i subscript absent inside the summation part? What's the reason behind this?

1

There are 1 answers

0
Sandipan Dey On

If you follow step by step from the below figure, it should be clear:

enter image description here