# 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++

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

## C

 `void``fun()``{``    ``int``i, j;``    ``for``(i = 1; i <= n; i++)``        ``for``(j = 1; j <= ``log``(i); j++)``            ``printf``(``"GeeksforGeeks"``);``}`

## Java

 `static``void``fun()``{``    ``int``i, 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

 `import``math``def``fun():``    ``i ``=``0``    ``j ``=``0``    ``for``i ``in``range``(``1``, n ``+``1``):``        ``for``j ``in``range``(``1``,math.log(i) ``+``1``):``            ``print``(``"GeeksforGeeks"``)` `# This code is contributed by SHUBHAMSINGH10.`

## C#

 `static``void``fun()``{``    ``int``i, 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)) `