0
for(i=n/2;i<=n;i++) {
    for(j=1;j<= n/2;j++) {
        for(k=1;k<=n;k=k*2) {
            statement;
        }
    }
}

what is the complexity for that code i think it would be in log with n^2 but i can't find it please answer me.

bhagyashri kshirsagar
  • 1
  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – devlin carnate Jul 29 '16 at 16:30

1 Answers1

0
for(i=n/2;i<=n;i++) {         // it is O(n)
    for(j=1;j<= n/2;j++) {    // it is O(n)
        for(k=1;k<=n;k=k*2) { // it is O(log n)
            statement;
        }
    }
}

so O(n^2 * (log n))

dmitry
  • 41
  • 6
  • i didn't understand how log n comes?can you explain it? – bhagyashri kshirsagar Jul 30 '16 at 17:01
  • Long answer you can find, for instance, here http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly?rq=1 Briefly, here the complexity is log2 n. So if n grows 8 times, you need (log2 8) more time (only in the last loop), i.e. computation takes 3 times more. – dmitry Jul 31 '16 at 20:03