Javascript Time Complexity Analysis

Question

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

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

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(2ⁿ). 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.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered May 12, 2018 at 2:30

Zach Jones

464 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Garrigan Stafford · Accepted Answer · 2023-10-17 18:16:30Z

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).

Collectives™ on Stack Overflow

Javascript Time Complexity Analysis

1

2

2 Answers 2

1.

2.

Comments

1

2

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1

2

2 Answers 2

1.

2.

Comments

1

2

Comments

Your Answer

Sign up or log in

Post as a guest

Related