CODEWITHSUNDEEP
javaalgorithmbig-otime-complexity
Shawniac
Shawniac

Reputation: 61

What is the big o notation of following functions

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 ;
}

Upvotes: 5

Views: 405

Answers (4)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

The first exercise:

enter image description here

The second exercise (very expensive algorithm, should be avoided):

Note that the general case execution is the one factorized by c, while the sole n! tells the number of base cases (ex5(0) == 1). Summing the both would gave the exact number of recursive calls.

enter image description here

Upvotes: 1

bcorso
bcorso

Reputation: 47068

In each case you just have to consider how many iterations happen within the for-loop.

  1. ex1 = O(log(n)) The for-loop iterates log3(n) times

    r = n/30 + n/31 + n/32 + n/33 + ... + n/3log3(n)

  2. ex5 = O(n!) The for-loop iterates n times for f(n) and each iteration calls f(n-1) so the total iterations is |f(n)| = n*|f(n-1)|, where |f(n)| = # of iterations in f(n). Using this recursively gives:

    |f(n)| = n|f(n-1)|
       = n(n-1)|f(n-2)|
       = n(n-1)(n-2)|f(n-3)|
       ...
       = n(n-1)(n-2)...(3)(2)|f(0)|
       = n!

Upvotes: 1

r3mainer
r3mainer

Reputation: 24557

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.

Upvotes: 4

hrv
hrv

Reputation: 955

The first one will execute till i < log_3(N) and this can be said to be O(log_3(N))

The second one seems to be recursion of recursions. The function seems to recurse i! times for each i < N.

F(3) = {F(2) + F(1)} + {F(1)}
F(4) = {F(3) + F(2) + F(1)} + {F(2) + F(1)} + {F(1}}

Upvotes: 0

Related Questions