==

1ifthenreturn

2ifandthenreturn

3ifandthenreturn

3ifandthenreturn

4ifthenreturnelsereturn

- Let and the number of bits (in binary-expansion) of and respectively. Give an upper bound for the number of reursive calls needed to compute ?
- Give an upper bound for the number of machine word operations needed for computing .

2008-01-31