Why is the time complexity for this O(n * m)?

Question

I was practicing calculating the big Oh for methods using the RAM model, and I'm having trouble understanding why the overall time complexity for this is n * m (the n refers to how many times the loop iterates). From my understanding, the first two lines in the method are just constants and the times loop has a complexity of O(n * however many steps are in the loop for each iteration). I understand that calling .max and .min have a combined complexity of O(n^2). So doesn't that mean that the overall time complexity calculation will look something like this?

line 1 = constants
line 2 = constants
line 3-7 = n * (n^2 + constants)
line 8 = constants
overall time_complexity = n^3 + constants = n^3

Below is the source code for the method that I'm analyzing:

 # O(n * m) naive solution
    def max_windowed_range(array, window_size)
      num_windows = array.length - window_size + 1
      best_range = nil

      num_windows.times do |i|
        window = array.slice(i, window_size)
        current_range = window.max - window.min

        best_range = current_range if !best_range || current_range > best_range
      end

      best_range
    end

To help the community understand your question better, consider clarifying what 'm' and 'n' mean in relation to your code. — Heinrich supports Monica, Nov 25 '19 at 17:35
@Heinrich Unfortunately the solution didn't provide any context about what m is :( I assumed that it had something to do with the window size. And I'll add an edit for what the n represents! — , Nov 25 '19 at 17:43
Question edited! The n represents how many times the loop iterates — , Nov 25 '19 at 17:44

Fabio · Answer 1 · 2019-11-25T18:19:33.593

2

Line array.slice(i, window_size) cannot be considered as a constant, because array.slice will iterate array at least once O(m),
when you put this inside loop it makes n * m, where
- n amount of iterations in num_windows.times loop
- m amount of iterations in array.slice internal loop

Amount of iterations inside array.slice probably will be equal [array.length, window_size].min

Line current_range = window.max - window.min will be just O(2*m), because min and max iterates array once

So for whole method you end up with O(n * 2m) and if we ignore constants - O(n * m)

edited Nov 25 '19 at 18:19

answered Nov 25 '19 at 18:11

Fabio

31,528
4
33
72

`array.slice`, `window.max`, and `window.min` are all O(m). Though I'm not sure `array.slice` iterates, it can also copy memory (technically O(m) but with a very different constant). It can also be just pointer references which are copy-on-write. I'm not sure which Ruby does. – Schwern Nov 25 '19 at 18:19
Yes, it copies the memory. `Array#slice` calls `rb_ary_aref` calls `rb_ary_aref2` calls `rb_ary_subseq` calls [`ary_make_partial`](https://github.com/ruby/ruby/blob/0e8219f591f3f17cb7ee361e8a60dbef08145883/array.c#L1109) which uses memcpy. Technically O(m), but it has a much lower constant than iterative `window.max/min` and will be swamped by their cost. – Schwern Nov 25 '19 at 18:26
Thank you for the explanation!! Both of these answers were more than enough! – Nov 25 '19 at 19:42

Schwern · Accepted Answer · 2019-11-25T18:34:20.037

We can simplify this to only the non-constant parts.

num_windows = array.length - window_size + 1

num_windows.times do |i|
  window = array.slice(i, window_size)
  current_range = window.max - window.min
end

For each element of array, O(array.length), it looks at a window_size chunk twice, 2*O(window_size). num_windows is n, window_size is m, so that's O(n*m) when array.length is significantly larger than window_size. We'll come back to that.

Perhaps we can see it clearer if we spell out max and min longhand.

num_windows = array.length - window_size + 1

# n times
num_windows.times do |i|
  # m times, but with a very, very low constant
  window = array.slice(i, window_size)

  # m times
  max = window.each_with_object(nil) { |n,m|
    m = n if !m && n > m
  }

  # m times
  min = window.each_with_object(nil) { |n,m|
    m = n if !m && n < m
  }

  current_range = max - min
end

num_windows.times starts us with O(n) where n = num_windows. Easy.

Each iteration grabs a window_size, or m, size window and then window.max and window.min have to scan window twice. That's O(m). Do that n times and it's O(n*m).

As Fabio notes, array.slice(i, window_size) is also O(m), but it uses memcpy which has such a low constant it will be totally swamped by window.min and window.max. We can ignore it. See https://stackoverflow.com/a/394654/14660 for more.

As a backup, we can plug some numbers in. (I realize I have an off-by-one error here with window_size. It's illustrative to realize that for the purposes of Big-O it doesn't matter. Also I'm lazy and don't want to recalculate.)

array.length = 1000
window_size = 10

num_windows = 990
990 * 2*10  = 19800 # actual
1000 * 10   = 10000 # O(n*m)

The numbers don't have to match, just the ratios as they change. Double the size of array.length, roughly double the cost.

array.length = 2000
window_size = 10
num_windows = 1990

1990 * 2*10 = 39800 # actual
2000 * 10   = 20000 # O(n*m)

Double the size of window_size, roughly double the cost.

array.length = 2000
window_size = 20
num_windows = 1980

1980 * 2*20  = 79200 # actual
2000 * 20    = 40000 # O(n*m)

But as window_size gets close to array.length we get closer to O(n).

array.length = 100
window_size = 99
num_windows = 2

2 * 2*99   = 396   # actual
100 * 99   = 9,900 # O(n*m)
100        = 100   # O(n)

Double the length and double the window_size, O(n*m) says we should be quadrupled. But we only triple which is getting closer to O(n).

array.length = 200
window_size = 198
num_windows = 3

3 * 2*198  = 1188   # actual
200 * 198  = 39600 # O(n*m)
200        = 200   # O(n)

Why is the time complexity for this O(n * m)?

2 Answers2