Question in computer science

$VI||$ Big OA lot of people will, for some reason, see the two calls to f and jump to O$($N$^(2)).$ This is completely incorrect. Rather than making assumptions, let's derive the runtime by walking through the code. Suppose we call f$(4).$ This calls f$(3)$ twice. Each of those calls to f$(3)$ calls f$(2),$ until we get down to f$(1).$

How many calls are in this tree? $($Don$\text{'}$t count!$)$

The tree will have depth N $.$ Each node $($i$.$e$.,$ function call$)$ has two children. Therefore, each level will have twice as many calls as the one above it$.$ The number of nodes on each level is:

$\backslash$table$[[$Level$,$# Nodes,Also expressed as$...,$Or$...],[0,1,,2^0$