so for the positive case you have that f(n) involves a check on n, which is constant time, a printline which is constant time, and then two calls to f(n-1)

so in this n positive case
f(n) = the constant stuff + 2\*f(n-1) = O(1) + 2\*f(n-1)

But don't the calls to f(n-1) create even more calls?

since it's recursive

Yep

Do I need some kind of formula to determine how many calls it will create?

so by using the same formula, f(n-1) = 2*f(n-2) + o(1)

plugging that in to what you had before:
f(n) = 2\*(2\*f(n-2) + O(1)) + O(1) = 2\*2\*f(n-2) + O(1)

ah, so it just simplifies to another logarithmic function?

yes

its exponential (the inverse of logarithm)

Okay. That should be enough to write up a logical explanation, I think. Apparently the other two function are easier to analyze.

Thanks a lot

```java
public void three(int n)
{
int i, j, k;
for (i = n/2; i > 0; i = i/2)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
System.out.println("i: " + i + " j: " + j+" k: " + k);
```

This is the next one. Should be easier for me to figure this one out since it's just for loops, right?

yes

```java
public static void four(int n)
{
if (n > 1)
{
System.out.println(n);
four(n-1);
}
for (int i = 0; i < n; i++)
System.out.println(i);
}
```

I'm pretty sure this one is just Nlog(N) but I might be wrong

idk I'll go try to figure this stuff out myself and come back if there's a problem

thanks

you're welcome

@ThisIsChris If there was only one call to two() rather than two calls, would that make it an O(n) function?

Since it just calls itself n times until it reaches the base case, and than calling itself twice each time

@Jacob yes

Thanks

so I guess the last function is O(n^2 log(n))

wait no

last one if O(n^2)

second one is O(n^2 log(n))

maybe that simplifies to something idk

@Jacob base case is f(1) = O(1)

for n > 1:
f(n) = f(n-1) + O(n)

so f(n) = sum over i from 1 to n of O(i)

sum of i from 1 to n of i = n*(n-1)/2

so f(n) = O(n^2)

^

you could also expand and see how much work is being done in each step

four(n) does a function call (O(1) not accounting for the recursion) and then prints n

if you expand that all the way, you'll see that it does n+(n-1)+(n-2)+...+2+1 print statements, which is O(n^2) as @ThisIsChris pointed out

that's another perspective that I use sometimes to calculate big Os

<@&435155896780324864> Lads, it's that time of week again