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

I came across this question and this is what I think. The outer loop will run, N/2 times and the inner loop will run logN times so it should be N/2*logN. But this is not the correct answer. The correct answer is O(NlogN), can anybody tell me what I am missing? Any help would be appreciated.

Manish Sundriyal
  • 611
  • 6
  • 16
  • 4
    What is the time complexity of your code? in your opinion and why? – Ami Hollander Mar 15 '18 at 21:35
  • @AmiHollander The outer loop will run, N/2 times and the inner loop will run logN times so it should be N/2*logN. But this is not the correct answer. – Manish Sundriyal Mar 16 '18 at 08:20
  • Those who have downvoted my question, I would request you guys to please comment the reason so I can learn the right way of posting questions. – Manish Sundriyal Mar 16 '18 at 08:23
  • 1
    @ManishSundriyal then this would give O(n.log(n)). Why you say it is not the correct answer? – Jean-Baptiste Yunès Mar 16 '18 at 11:02
  • @ManishSundriyal you need to explain in the question, what is your opinion? ask how to solve a problem? and not ask for the answer, your commect could appear in the question and it would have been much better... why is not O(n log(n))? – Ami Hollander Mar 16 '18 at 18:44
  • @ManishSundriyal A good question would include something like "I think the answer is x, but my professor told me that y is the correct answer; so can you help me understand if s/he is right, and what I am missing?" I think editing your question to include this will have people upvote it to offset the downvotes. So what is the correct answer that is given to you? nlogn? – FatihAkici Mar 16 '18 at 21:50
  • @AmiHollander thank you very much for pointing out that – Manish Sundriyal Mar 17 '18 at 11:58
  • 1
    @FatihAkici thank you too for explaining the right way – Manish Sundriyal Mar 17 '18 at 11:59
  • @Jean-BaptisteYunès It was O(n/2.log(n)) according to me. But now I have known why it is O(n.log(n)) and not what I was thinking. – Manish Sundriyal Mar 17 '18 at 12:07
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Mark Rotteveel Mar 17 '18 at 12:13
  • @ManishSundriyal You're welcome. (n/a)*log(n)+b is nlog(n), because those constants are always omitted per the mathematical definition of big-O. – FatihAkici Mar 17 '18 at 14:40

1 Answers1

0

Let's take a look at this block of code.

First of all, you can notice that inner loop doesn't depend on the external, so the complexity of it would not change at any iteration.

for (j = 2; j <= n; j = j * 2) {
    k = k + n/2;
}

I think, your knowledge will be enough to understand, that complexity of this loop is O(log n).

Now we need to understand how many times this loop will be performed. So we should take a look at external loop 

for (i  = n/2; i <= n; i++) {

and find out, that there will be n / 2 iterations, or O(n) in a Big-O notation.

Combine these complexities and you'll see, that your O(log n) loop will be performed O(n) times, so the total complexity will be O(n) * O(log n) = O(n log n).

DoomzDay
  • 39
  • 4