3

I was reading this question, and this comment in precise captured my attention Stackoverflow

The comment says that in order to achieve O(n log n) we would need the outer loop to be: for(int i = 0; i < n; i++) and the nested loop to be: for(int j = n; j > 0; j/=2), which makes the nested loop domain: from n to n/2.

I understand that the to find the time complexity, we take into consideration the input size, and the number of steps it takes to run the computation, but it seems to me that it depends solely on the step-through portion, and how to minimize the number of steps to get from 0 to n (or vice versa). Is my understanding correct ?

If this is true, then changing the nested loop to for(int j = n/2; j > 0; j--) or for(int j = n/4; j > 0; j--)( which would make the the domain between 0 and n/2 or n/4 respectively) would still keep the algorithm complexity time n*(n/2) or n*(n/4) = n^2

I appreciate any explanation.

USR67252
  • 31
  • 2
  • 1
    "*Time complexity of an algorithm depends on the incremental/decremental step portion, and not the actual input size?*" - yes. If you want to sum all the elements from the input, it will be a linear (`O(n)`) operation. It doesn't matter whether there are `10`, `100` or `100000` elements. The function stays linear. You simply put these `10`, `100` or `100000` into the function `f(x)` and get `f(10)`, `f(100)` or `f(100000)`. – Fureeish Dec 12 '19 at 17:28

2 Answers2

2

...which makes the nested loop domain: from n to n/2.

That's not quite right. The loop still goes from n to 0; the domain hasn't changed. What has changed is how it gets there. It doesn't subtract one each iteration, which would mean it would take n steps. It divides j in half each iteration.

How many times can you divide a number in half before reaching 0? Well, if you start at n then it takes O(log2 n) steps.

  • 4 → 2 → 1 → 0 = 3 steps
  • 8 → 4 → 2 → 1 → 0 = 4 steps
  • 16 → 8 → 4 → 2 → 1 → 0 = 5 steps
  • 32 → 16 → 8 → 4 → 2 → 1 → 0 = 6 steps

Every time you double n it takes one more step. Classic exponential/logarithmic relationship.

The lesson is: there's a very big difference between having the division in the iterated step...

for(int j = n; j > 0; j/=2)       // O(log n)

...and having it in the starting or ending bounds:

for(int j = n/2; j > 0; j--)      // O(n/2) = O(n)
for(int j = n; j > n/2; j--)      // O(n/2) = O(n)
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • Thanks for the explanation, so how we take those steps is what determines the time complexity since it will set the approximate time(aka mathematical relationship) it takes to go from n to 0? – USR67252 Dec 12 '19 at 17:55
  • @USR67252 it is both the domain and the "increment"/step. `for(int j = n; j > 0; j/=2)` is `O(log n)` (neglecting the complexity of the loop body), and so is `for(int j = log2(n); j > 0; j--)`. – EvilTak Dec 12 '19 at 23:25
1

In that for-loop, every time we update the value of j to be half of its previous value.

So the number of steps taken will be log(n) and the domain is not n to n/2 but n to 0 as the for-loop runs until j > 0.

b_hunter
  • 9
  • 1