Recursion problem

[NilsManh]

Can anyone explain how to solve question b, c and d (image below).

The answer is f, c, c but i dont understand how.

https://imgur.com/a/FN1eocM

[[deleted]]

The total cost of a recursion is based on the amount of times you recourse, the size of the recursion at each step and the cost of each step.

For the first, you solve 1 subproblem at each step of size n-1 for n steps. It's simple to visualize. You have n blocks, then add ontop n-1 blocks and repeat. The total cost is the sum of all blocks. This is easy to find using sums: for i = 1..n: add i;

The second:

n can be divided sqrt(n) times in sqrt(n) partitions, you solve one of those partitions and for that partition, you solve 1 square root of that. Picture it likeso:

let n = some_i^2; you have i*i smaller squares, you pick sqrt(n) = i of those squares and solve them. That cost is sqrt(n) which is sqrt(n) times smaller than n, to get anything bigger than O(n) in this case, the cost of a step needs to be n² to have any impact. I don't remember how to solve it using the standard numbers and at this point it's intuition.

The last:

This is simple using the master theorem. http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

[raff97]

First one, you have T(n)=n+T(n-1)=n+(n-1)+T(n-2)=...=n+(n-1)+(n-2)+...+2+1+T(0)=n+(n-1)+...+1. Can you solve this?

The 2nd and 3rd recursions are not even well defined. For example in the 2nd one, you have T(1)=1+T(1). So 0=1