What's the complexity of this loop

Question

I'm trying to figure out what's the time complexity of this code that solves the sliding maximum problem

I tried with 2 nested loops but that would be of the complexity O(n*k) and I think that the code listed below is less complex

  res=[]
  for i in 0..(array.length-k) do 
   res <<  array.slice(i,k).sort[-1]
  end
  return res 

I want to know what is the complexity of the used default methods (Ruby) and how they affect this loop's complexity. Thanks

Answer 1

Here is another benchmark, one that shows how relative efficiency changes as k (size of each slice) increases.

require 'benchmark'

def test(arr, k)
  puts "Testing for k = #{k}"
  Benchmark.bm(11) do |x|

    x.report("Wonder Boy") {
      res=[]
      for i in 0..(arr.length-k) do
        res << arr.slice(i,k).max
      end
      res
    }

    x.report("Tadman") { arr.each_cons(k).map(&:max) }

    x.report("Cary") {
      (k..arr.size-1).each_with_object([arr.first(k).max]) do |i,a|
        mx = a.last
        a << (arr[i-k] < mx ? [mx, arr[i]] : arr[i-k+1, k]).max
      end
    }

    x.report("Engineer 1") {
      a = arr.dup
      b = a.shift(k)
      max_n = n = b.max
      Enumerator.new do |y|
        y << max_n
        loop do 
          break if a.empty?
          b.<<(a.shift)
          max_n = b.max if b.shift == max_n || b.last > max_n
          y << max_n 
        end
      end.to_a    
    }

    x.report("Engineer 2") {
      a = arr.dup
      b = a.shift(k)
      max_n = n = b.max
      Enumerator.new do |y|
        y << max_n
        loop do 
          break if a.empty?
          b.<<(a.shift)
          max_n = (b.shift == max_n) ? b.max : [max_n, b.last].max
          y << max_n 
        end
      end.to_a    
    }
  end
end

arr = 10000.times.map { rand(100) } 
arr.first(4)
  #=> [61, 13, 41, 82]

test(arr, 3)
Testing for k = 3
                  user     system      total        real
Wonder Boy    0.021185   0.004539   0.025724 (  0.025695)
Tadman        0.004801   0.000000   0.004801 (  0.004809)
Cary          0.004542   0.000000   0.004542 (  0.004568)
Engineer 1    0.003998   0.000000   0.003998 (  0.004005)
Engineer 2    0.003427   0.000000   0.003427 (  0.003438)

test(arr, 10)
Testing for k = 10
                  user     system      total        real
Wonder Boy    0.003102   0.000000   0.003102 (  0.003105)
Tadman        0.003205   0.000012   0.003217 (  0.003225)
Cary          0.003286   0.000000   0.003286 (  0.003292)
Engineer 1    0.003387   0.000000   0.003387 (  0.003397)
Engineer 2    0.003092   0.000000   0.003092 (  0.003100)

test(arr, 30)
Testing for k = 30
                  user     system      total        real
Wonder Boy    0.011111   0.000000   0.011111 (  0.011139)
Tadman        0.010568   0.000000   0.010568 (  0.010572)
Cary          0.004292   0.000000   0.004292 (  0.004301)
Engineer 1    0.004197   0.000000   0.004197 (  0.004203)
Engineer 2    0.003759   0.000000   0.003759 (  0.003766)

test(arr, 100)
Testing for k = 100
                  user     system      total        real
Wonder Boy    0.007409   0.000035   0.007444 (  0.007437)
Tadman        0.005771   0.000914   0.006685 (  0.006703)
Cary          0.002773   0.000000   0.002773 (  0.002782)
Engineer 1    0.003213   0.000000   0.003213 (  0.003222)
Engineer 2    0.003138   0.000005   0.003143 (  0.003150)

test(arr, 1000)
Testing for k = 1000
                  user     system      total        real
Wonder Boy    0.019694   0.000000   0.019694 (  0.019696)
Tadman        0.031178   0.012383   0.043561 (  0.043571)
Cary          0.005782   0.000000   0.005782 (  0.005788)
Engineer 1    0.002446   0.000000   0.002446 (  0.002431)
Engineer 2    0.002395   0.000000   0.002395 (  0.002396)

The most indicative result is almost certainly the one for k = 100.