Will both function have same Time Complexity?

Question

Will both these function have O(nlogn) time complexity ?

function loop1(arr) {
    for (let i = 0; i<arr.length; i++){
        for (let j=i; j<arr.length; j++){
            console.log(arr[j])
        }
    }
}

function loop2(arr) {
    for (let i = 0; i<=arr.length; i++){
        for (let j=1; j<=Math.log(i); j++){
            console.log(arr[j])
        }
    }
}

Can you describe what those functions do. They seems to have different results, is it intended ? — Portevent, Oct 19 '22 at 13:14
@Portevent Yes, I just came across these 2 algos in a book about JavaScript where the Output for both was asked but I could not figure out the time complexity — YRR, Oct 19 '22 at 13:17
I would call the first one `O(n * n)`, as the number of iterations of the inner loop clearly grows in a way proportional to the size of `n`. — Pointy, Oct 19 '22 at 13:19
@Pointy yeah got it, the second loop would be O(n * log(n)) ? — YRR, Oct 19 '22 at 13:27
@YRR yes I think so, though as noted it's kind-of a weird thing to do. I suppose there might be a practical use for it. — Pointy, Oct 19 '22 at 13:32

score 2 · Accepted Answer · answered Oct 19 '22 at 14:51

No.

Your first code will run

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

iterations (see arithmetic progression).

Your second code runs

0 + floor(log(1)) + floor(log(2)) + ... + floor(log(n)) <= log(1) + log(2) + ... log(n) = log(n!) = O(n logn)

iterations (see this question).

Notice also that your second code, first iteration, computes Math.log(0), which in javascript returns -Infinity so it works for this case, but in mathematics it is not defined.

Will both function have same Time Complexity?

1 Answers1