-1

What is the time complexity of the following code snippet and how to calculate it.

 function(int n){
        for(int i = 1 ; i<=n ; i++){
            for(int j=1 ; j<=n; j+=i){
                System.out.println("*");
        }
    }
kverma28
  • 57
  • 1
  • 13
  • You need to show what you've done and specifically where you're stuck rather than expecting other people to do your homework for you. – code_dredd Aug 12 '16 at 09:57
  • Q: `How to find the time complexity of the following code snippet` A: By calculating it. (and less trolling: What do **you** think it is?) – amit Aug 12 '16 at 10:03
  • Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – amit Aug 12 '16 at 10:13
  • When i = 1, inner loop will iterate n times, when i = 2, inner loop will iterate n/2 times, when i=3, inner loop will iterate n/3 times...and so on. So total number of iteration in this case will be n+n/2+n/3+n/4+n/5+....upto n terms.......So what would be the final complexity according to this approach....???? – kverma28 Aug 12 '16 at 13:52

1 Answers1

1

Let's think about the total work that's done. As you noted in your comment, the inner loop runs n times when i = 1, then n / 2 times when i = 2, then n / 3 times when i = 3, etc. (ignoring rounding errors). This means that the total work done is

n + n/2 + n/3 + n/4 + ... + n/n

= n(1 + 1/2 + 1/3 + 1/4 + ... + 1/n)

The term in parentheses is the nth harmonic number, denoted Hn, so the work done overall is roughly nHn. It's known that Hn = Θ(log n), so the total work is Θ(n log n).

Community
  • 1
  • 1
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    Sure! Check out slides 107-115 of [these slides](http://www.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/10/Slides10.pdf). – templatetypedef Aug 16 '16 at 16:10