Skip to content
Related Articles

Related Articles

Improve Article
Save Article
Like Article

A Time Complexity Question

  • Difficulty Level :Easy
  • Last Updated :27 Dec, 2021

What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2. 

C++




voidfun()
{
    inti, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= log(i); j++)
            cout << "GeeksforGeeks";
}
 
// This code is contributed by SHUBHAMSINGH10.

C




voidfun()
{
    inti, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= log(i); j++)
            printf("GeeksforGeeks");
}

Java




staticvoidfun()
{
    inti, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= log(i); j++)
            System.out.printf("GeeksforGeeks");
}
 
// This code is contributed by umadevi9616

Python3




importmath
deffun():
    i =0
    j =0
    fori inrange(1, n +1):
        forj inrange(1,math.log(i) +1):
            print("GeeksforGeeks")
 
# This code is contributed by SHUBHAMSINGH10.

C#




staticvoidfun()
{
    inti, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= log(i); j++)
            Console.Write("GeeksforGeeks");
}
 
// This code is contributed by umadevi9616

Javascript




const fun()
{
    let i, j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= Math.log(i); j++)
            document.write("GeeksforGeeks");
}
 
// This code is contributed by SHUBHAMSINGH10.

Time Complexity of the above function can be written as θ(log 1) + θ(log 2) + θ(log 3) + . . . . + θ(log n) which is θ(log n!)
Order of growth of ‘log n!’ and ‘n log n’ is same for large values of n, i.e., θ(log n!) = θ(n log n). So time complexity of fun() is θ(n log n).
The expression θ(log n!) = θ(n log n) can be easily derived from following Stirling’s approximation (or Stirling’s formula)

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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Sources: 
http://en.wikipedia.org/wiki/Stirling%27s_approximation


My Personal Notesarrow_drop_up
Recommended Articles
Page :

Start Your Coding Journey Now!