CODEWITHSUNDEEP
algorithmruntime
Kuno Heltborg
Kuno Heltborg

Reputation: 71

Algorithm runtime

enter image description here

Can you please help me with calculating the running time of this function?

My guess would be O(n log n) n for the for-loop, and log n for the while loop.

But what makes me unsure is the j = j*3. if it would have been j = j/2, then I would have been sure of my answer.

Is it log n even though it is j = j*3 or j = j/3?

Upvotes: 2

Views: 110

Answers (3)

Shubham
Shubham

Reputation: 2855

If it's j = j*3, then the complexity will just be O(n*log_3(n)) instead of O(n*log_2(n)) for j = j*2 because they only differ by a constant factor which will be absorbed under Big-O notation.

Coming to your function, the outer loop is surely O(n) but the inner loop is not completely log_3(n) every time. It's actually decreasing with every iteration. The expansion will be:

log_3(n) + log_3(n-1) + log_3(n-2) + ... + log_3(1)

Ignoring bases because of the reason explained above, we can write:

log(n) + log(n-1) + log(n-2) + ... + log(1)

  • One method to evaluate this is to upper bound each of the above terms by log(n), i.e., 

    log(n) + log(n-1) + log(n-2) + ... + log(1) <= log(n) + log(n) + log(n) + ... + log(n)
                                            <= n*log(n)

    Thus, the complexity can be written as O(n*log(n)).

  • Second method is as follows. Rewriting the above equation, we have:

    log(n) + log(n-1) + log(n-2) + ... + log(1)
= log(n*(n-1)*(n-2)...1)
= log(n!)

    Thus, for sure, the complexity can be written as O(log(n!)). But what about log(n!)? According to Stirling's approximation, 

    log(n!) ~ n*log(n) - n + O(log(n))

    Note that, according to Wikipedia:

    It is a very powerful approximation, leading to accurate results even for small values of n.

    Thus, I can assume that this will be very much accurate for large values of n (the case that we actually care about). Clearly, in the above approximation, the value of n*log(n) dominates the other terms, thus, in Big-O notation, I can write:

    O(log(n!)) = O(n*log(n))

Upvotes: 1

Yar
Yar

Reputation: 195

A tighter upper-bound would be O(n). Because the total time is ( Sum(i=1 to n) of (log(n/i)) ) = log(n^n/n!) = O(n) The running time is actually Θ(n) if that matters.

Upvotes: 1

Cherkesgiller
Cherkesgiller

Reputation: 520

Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example :

   for ( int i = 1; i <= n; i ++ ) {
   for ( int j = 1; j <= n; j ++ ) {
      // O(1) expressions
   }

}

In this situation (log_3(n)) you can test it with a small c++ code like this:

int main()
{
    const int N = 10;
    int j;
    int count = 0;
    int totalCount = 0;

    for ( int i = 1; i <= N; i++ ) {
        j = i;
        while ( j <= N ) {
            j = j * 3;
            count++;
        }
        std::cout << " " << i <<"th iteration of outer loop : inner loop will iterate " << count << " times" << std::endl;
        totalCount += count;
        count = 0;
    }
    std::cout << "TOTAL COUNT is : " << totalCount << std::endl;
    return 0;
}

Where you get results like this: 

1th iteration of outer loop : inner loop will iterate 3 times
2th iteration of outer loop : inner loop will iterate 2 times
3th iteration of outer loop : inner loop will iterate 2 times
4th iteration of outer loop : inner loop will iterate 1 times
5th iteration of outer loop : inner loop will iterate 1 times
6th iteration of outer loop : inner loop will iterate 1 times
7th iteration of outer loop : inner loop will iterate 1 times
8th iteration of outer loop : inner loop will iterate 1 times
9th iteration of outer loop : inner loop will iterate 1 times
10th iteration of outer loop : inner loop will iterate 1 times
TOTAL COUNT is : 14

Upvotes: 0

Related Questions