CODEWITHSUNDEEP
javascriptarraystimetime-complexitybig-o
QGuy123
QGuy123

Reputation: 21

Javascript Time Complexity Analysis

Hi there I have been researching and trying to learn how to check for the time complexity of certain algorithms. I've seen this video which was very helpful.

That being said I wondered off and started trying to work out the Worsts Case and an average case of certain algorithms.

1

I believe in the following snippet it is O(n) since to ind the value for sin we have to loop the entire array.

function mySin(x, iterNum) {
    var mxx = -x*x;
    var sin = 1;
    var n = 0;
    var term = 1;
    for (var i = 1; i <= 2*iterNum; i++) {
        n = n + 2;
        term = term * mxx / ( n*(n+1) );
        sin = sin + term
    }
    sin = x*sin;
    console.log(sin + " = my function.");
    console.log(Math.sin(x)  + " math.sin");
}

Thanks again

2

function calculateFibonacciSum (num) {
    if(cachedNumbers[num]) {
        return cachedNumbers[num];
    }
    if(('number' === typeof num) && num <= 0) {
        throw new Error ('Fibonnci series starts with 0. Please, enter any interget greater than or equal to 0');
    }
    else if(('number' === typeof num) && num === 0) {
        return 0;
    }
    else if(('number' === typeof num) && (num === 1 || num === 2)) {
        return 1;
    }
    else {
        var value = calculateFibonacciSum(num-1) + calculateFibonacciSum(num-2);
        cachedNumbers[num] = value;
        return value;
    }
}

While for this one I think it is also O(n) since in the first if/else statement the tc is O(1) since its contestant whilst the final else statement we must loop all the numbers and if the number is not calculated then call the function again (aka recurssion).

TIA

Upvotes: 1

Views: 291

Answers (2)

Garrigan Stafford
Garrigan Stafford

Reputation: 1403

1

This is in fact O(k) becuase if we pass in k for iterNum we get 2*k iterations with each iteration having a constant, say l arithmetic operations. So the total cost is something like l*2*k which is O(k) since l is constant.

2

This is an example of amortized cost. The worst case is when the cache is empty originally starting with n. Then you will need to make n recursive calls, however each call will fill its cache, so when the other recursive calls reach that point it just immediately returns.

So basically the call calculateFibonacciSum(num-1) will need to happen all the way down to calculateFibonacciSum(1), but it will fill the cache along the way which means calculateFibonacciSum(num-2) will just look up the cache. This gives us n recursive calls each with constant time so O(n).

With the amortization though your average time can approach O(1), depending on how you are calling the function. If you are just calling with increasing n each time then it is still O(n), but if you are calling with random n or with values of n close to each other it will average out to O(1).

A way to think about it is that calculateFibonacciSum(n) will make as many recursive calls between the highest value in the cache , say k, and n cause those are the uncalculated values in the chain. So that gives you n-k calls. However if n<k it just looks up the cached value giving O(1).

Upvotes: 0

Zach Jones
Zach Jones

Reputation: 46

Both of these seem correct to me. Here's a bit more explanation:

1.

This is in fact O(n), as there are n iterations of the loop, the rest constant time; and n is proportional to iterNum

2.

This one is also linear time, but only since you cache the results of previous calculations. Otherwise it would be O(2n). It is linear time since it essentially runs a loop down to the base cases (0 and 1). In fact, you could re-write this one using a loop instead of recursion.

Upvotes: 1

Related Questions