[Reincarnate]

static long Fibonacci(int n) {
    if (n==1||n==2) return 1;
    return Fibonacci(n-2)+Fibonacci(n-1);
}

Without memoization, I'd say O(2^n). I know there's something called the Master Theorem that can be used for linear recurrences but I haven't learned it yet.

With memoization, O(n)

for (int i=0,j=0; i<n; i++)
    for (double d=1; d<n; d*=2)
        j++;

O(n log n)

int[] a=new int[n];
for (int i=4;i<n;i++) {
    for (int j=i-3,sum=a[i-4];j<=i;j++)
        sum+=a[j];
}

what the fuck this code lol
uhh, O((n-4)*4) = O(4n-16) = O(4n) = O(n)?

private static long gcd(long n,long r) {
    if (r==0) return n;
    return gcd(r,n%r);
}

mofuggin euclidean algo ftw
and yet I have no idea its runtime. hmmm.
I don't know what the runtime contribution is like for the modulus operation, which in itself can be pretty expensive IME. I'll ignore it.
Overall though I'll just say log n, feels right but I don't know how to really prove that rigorously