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
  • 16,433
  • 23
  • 85
  • 123
Ivan Sivak
  • 7,178
  • 3
  • 36
  • 42
  • 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
  • 49,595
  • 11
  • 110
  • 380