What is the big o notation of following functions
algorithm, big-o, java, time-complexity
Solution
The output values of ex5 correspond to sequence A000522 at oeis.org, which increases as a(n) = Sum_{k=0..n} n!/k! (or n! to a first approximation). Because of the horrible way this function is coded, this is equal to the function's time complexity.
A much better algorithm would be as follows:
public static int ex5 ( int n ) {
return (n) ? 1 + n * ex5(n-1) : 1;
}
which is obviously O(n^2) O(n) (Sorry, it's late and I need sleep!).
EDIT: As everyone else is saying, the complexity of ex1 is O(log_3(n)), or simply O(log(n)), since log_3(n) = log(n)/log(3), and log(3) is a constant in any base.
Problem
I can't figure out the smallest upper barriers for those two functions. I think ex1 has `O(log_3(n))` and ex5 should have `O(n!)`. But I'm not actually confident about this, since I haven't truly understood the subject yet. ``` public int ex1 ( int n ) { int r = 0 ; for ( int i = 1 ; i < n ; i++) { r += n ; n = n / 3 ; } return r ; } ``` ``` public static int ex5 ( int n ) { int r = 1 ; for ( int i = 0 ; i < n ; i ++) { r += ex5 ( n - 1 ) ; } return r ; } ```