CODEWITHSUNDEEP
algorithmtime-complexitybig-o
J. Uchu
J. Uchu

Reputation: 121

Is the measurement of the big O notation correct in my algorithm?

Here is the link to algorithm without comments, to see better

function getLastFactor(n) {
 var tempArr = [2, 3], max = Math.sqrt(n); /* (1 + 1) 
 it is despised
 */
 for(var i = 5; i < max; i += 2) { /* 
 (sqrt(n) - 5)  ---> ( 5 is despised )
 */
  if(n%i) continue; /* 
  sqrt(n) - 5 operations 
  PD: Should I add this? or is it already included in the for, in (sqrt(n) - 5 above) ?
 */
  if(check(tempArr, i)) continue; // How do I measure this? If I do not have security of the number?
  tempArr.push(i); // 1 operation it is despised
 }
 return tempArr[tempArr.length - 1]; // 1 operation
}

function check(array, i) {
 for(var j = 0, l = array.length; j < l; ++j) { // sqrt(n) operations 
  var cur = array[j]; // 1 operation
  if(!(i%cur)) return true; // 1 operation
 }
 
// O(3 * sqrt(n))

I do not know what really add up, I have read that that is not important, since the Big O notation standardizes that, eliminating the terms of minor order. But I have many doubts, like some that I left in the code itself and also:

This problem is not a duplicate of another, I have read a lot by the network and especially in this community, and almost all the questions / answers are based on the theoretical and almost never have seen theoretical and practical examples at the same time.

Upvotes: 0

Views: 46

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15261

First of all, when using big-o notation drop all constants, so O (sqrt (n) * 3) is actually O (sqrt (n)).

To correctly analyze the asymptotic complexity of this code we need some background in number theory. What this algorithm basically performs is determining the prime factors of n (only the greatest is returned). Main part of program is a for loop that iterates over all odd numbers from 5 to sqrt(n), so the number of iterations is (sqrt(n) - 5) / 2, or in big-o terminology, O(sqrt(n)).

Next, there is a statement if(n%i) continue; that eliminates all numbers that are not divisors of n (regardless whether they are prime or not). So, the rest of code is executed only when i is a divisor of n. Asymptotic bound for number of divisors is O(n^{1 / ln(ln(n))}).

Finally, there is a function check that iterates over the array tempArr which contains prime divisors of n found so far. How many prime divisors does a positive integer n have? Asymptotic bound for number of prime divisors is in a worst case (when n is so called a primorial number) O(ln(n) / ln(ln(n))).

Let's now sum up everything. Even if we assume that n is primorial and that all prime divisors are found quickly (so array.length has a maximum possible value), the asymptotic complexity of the part of code after if(n%i) continue; is O(n^{1 / ln(ln(n))} * ln(n) / ln(ln(n))). It is not that easy to see, but this grows slower than O(sqrt(n)), so the total complexity is O(sqrt(n)).

Upvotes: 1

Related Questions