2

The recurrence relation you give can be handled by the master theorem. Any proof of the master theorem will include similar steps (in more generality). A good proof of the master theorem should carefully explain all the steps in the proof. Beware, though, that the master theorem includes three different cases, and you're interested in only one of them (case ...


1

You are right that in order to analyze the recurrence, you need to take two parameters into account: the original list size $N$, and the size of the sublist currently operated on $n$. In terms of these parameters, the running time is $\Theta(N2^n)$. However, what we are really interested in is the running time of the algorithm when running on the entire list ...


1

Fix a value of $j$, i.e., an iteration of the outer loop. If the condition of the while loop at line 5 is tested $t_j$ times during this iteration (as per definition) then it must be false exactly once. In particular, it must be false in the last of the $t_j$ tests, which causes the inner while loop to terminate. As a consequence, each instruction in the ...


1

With your assumption that computing $x^i$ has $O(i)$ complexity, the iteration with some $i$ will have complexity of $O(i)$ too (it simply adds $x^i$ to the current sum). So, complexity of each iteration can be taken $ci$ for some $c$. Total complexity of all iterations: $ \sum_{i=1}^{n} ci = cn(n+1)/2 $ which belongs to $O(n^2)$. But for an efficient method,...


Only top voted, non community-wiki answers of a minimum length are eligible