2

I would need to determin the Big O of this short code:

var iterations = 0;

function operation(num){
    iterations++;
    if (num == 0) return 1;
    return operation(Math.floor((num / 10) * 2));
}

var result = operation(1000);

alert('Result = ' + result + ', number of iterations = ' + iterations);

I came up with something around O(log(logN)) but I'm not sure. Would you please help me a bit?

http://jsfiddle.net/qotbu5pq/2/

Nikolay Kostov
  • 15,454
  • 21
  • 81
  • 119
Ivan Sivak
  • 6,628
  • 3
  • 32
  • 40
  • 1
    Please tell us how you got to `O(log(log(N)))` and we'll be able to tell you where you went wrong. – Bergi Feb 13 '15 at 11:01
  • 3
    There is a great way to approximate it here: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – m0bi5 Feb 13 '15 at 11:02
  • 3
    you are almost dividing operations by 5 until hit the zero result so should not it be `~log5(N)` iterations instead which means `O(log(N))` ... – Spektre Feb 13 '15 at 11:17
  • @Spektre It is the needed answer, and should be set as such. :-) – Gangnus Feb 13 '15 at 11:50

1 Answers1

3

[Answer from comment]

  • you are almost dividing operations by 5 until hit the zero result
  • so should not it be ~log5(N) iterations instead which means O(log(N))
  • sorry didn't want to add such trivial answer ...
Spektre
  • 45,598
  • 10
  • 100
  • 347