What's the Big O of this function?

can you figure out the big O of this recursive function I'm Tara, I'm a senior software engineer and I used to teach computer science at Carnegie Mellon So the runtime of a recursive algorithm is equal to the number of nodes in its recursion tree multiplied by the work per node. And you can think of the number of nodes in the recursion tree as being like the number of recursive calls that we make. I started off n as 10 here and I didn't even really have space to draw the whole tree. Oh, speaking of trees, I am doing a coding competition related to trees. Go win my coding contest: www.tarabyte.tech You can check it out on my website, the deadline is January 11th. Really what I want to find out is how many nodes are in this tree. And the tree is a binary tree because from each call we make two more recursive calls. So when we're at 10 here, we make the calls for n minus 1, which is 9 and n minus 2, which is 8. Until we get down to our base case when n is less than or equal to 1. So we need to know two things to solve that. We need to know how tall is this binary tree and then how many nodes are on each level of the tree. So I can say right now, this is gonna go all the way down. So we're gonna get like a 6 here, a 5, 4, 3, 2 and 1 node going all the way down this side of the tree. Like this tree is not perfectly balanced on this side. We like subtract 2 every time. But because we're thinking of big O, we're thinking about like the worst case scenario. So I'm just gonna go ahead and say that the height of this tree is actually N. So then the question is, how many nodes are on each level of the tree? Well, on the first level, there is one node. On the second level, there are two nodes. On the third level, there are four nodes. On the fourth level, there are eight nodes. Take a wild guess for how many nodes are on the fifth level. Can you see what the function is here? For every level of the tree, we can get the number of nodes by saying it's two to the i where i is the level that we're on. And we go all the way up to N. So then what does this thing look like? Well, it's gonna be like 1 + 2 + 4 + ... + 2 to the N. I really need to get an iPad or something. Apple, you wanna sponsor me? So basically the runtime here is exponential because the total work is the sum 1 + 2 + 4 + ... + 2 to the N. And in big O world, the highest order term dominates. So this is O of 2 to the N. This is exponential. How would you change this code to make it so this is O of N instead of O of 2 to the N? If you've been watching my videos, you should know the answer to this. Alright, leave me a comment below.