Message from @ThisIsChris
Discord ID: 506666605015597076
Not necessarily expecting an answer to the question from anyone, but maybe something that can get me in the right direction
f(0) = O(1)
f(|n|) = 2*f(|n|-1) + O(1)
😬
so f(n) = O(2^n)
Is that the equation for this particular function?
yep
How would I go about getting that?
So start by looking at the function to understand what is the "base case". The base case is the input that doesn't cause a recursive call
ah, okay
and write the base case as one of those formulas?
the only input that doesn't have a recursive call is n=0
yep
so how do I move up from there?
So after that you really have two cases, one when n is > 0 and one when , is < 0. If you look closely what you have in each case is that n decreases or increases towards 0 with steps of 1. I'm just here pointing out the two cases. For simplicity consider what happens in just the positive case first
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?
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