Big O Complexity of Algorithm

Question

This method seeks to express num as a product of elements in arr.

For e.g method1(37,[1,3,5]) returns [2,0,7]

// arr is an array of divisors sorted in asc order, e.g. [1,3,5] 
def method1(num, arr) 
  newArr = Array.new(arr.size, 0)
  count = arr.size - 1

  while num > 0
    div = arr[count]  

    if div <= num
      arr[count] = num/div
      num = num % div
    end 

    count = count - 1
  end 

  return newArr
end 

Would really appreciate if you could give me some help to derive the complexity of the algorithm. Please also feel free to improve the efficiency of my algorithm

Answer 1

Here's what you can do:

def method1(num, arr)

    newArr = Array.new(arr.size, 0)
    count = arr.size()-1

    while num>0
        div = arr[count]

        if div <= num
            arr[count] = num / div
            num = num % div
        end

        count = count + 1
    end
    return arr
end


ar = Array.new(25000000) { rand(1...10000) }

t1 = Time.now
method1(37, ar)
t2 = Time.now

tdelta = t2 - t1

print tdelta.to_f

Output:

0.102611062

Now double the array size:

ar = Array.new(50000000) { rand(1...10) }

Output:

0.325793964

And double again:

ar = Array.new(100000000) { rand(1...10) }

Output:

0.973402568

So an n doubles, the duration roughly triples. Since O(3n) == O(n), the whole algorithm runs in O(n) time, where n represents the size of the input array.