CODEWITHSUNDEEP
javascripttime-complexitybig-ospace-complexity
Anas
Anas

Reputation: 15

How to figure out time complexity for a while loop nested in a for loop?

So I have this code here and I am just trying to understand the time and space complexity.

for time complexity I think its O(n^2) because it is going through at most n - 1 loops in the while loop and it will go through n times in the for loop so it will be O(n(n-1)) which is O(n^2) and space complexity I think its O(n) because it is linear space.

I don't know if I'm right but if I am wrong can someone correct my thinking? Thanks in advance.

    // Write your code here
    let visited = new Array(s.length).fill(false);
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        let j = i + 1;
        visited[i] = true;
        while (j < s.length && s[j] === s[i] && !visited[j]) {
            visited[j] = true;
            count++;
            j++;
        }
    }
    return count;

Upvotes: 1

Views: 746

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 370699

This is O(n) in time complexity, because:

while (j < s.length && s[j] === s[i] && !visited[j]) {

For this condition to be fulfilled, visited[j] needs to be false, and when it does get fulfilled, you then do

visited[j] = true;

So, that above line can only run as many times as there are items in the visited array. If the while loop runs to the end the first outer iteration (when i is 0), then it'll never run in any of the other outer iterations. If the while loop runs halfway through visited the first iteration, and through the other half the second iteration, it'll never run for the rest of the outer iterations. So, this part of the code:

    while (j < s.length && s[j] === s[i] && !visited[j]) {
        visited[j] = true;
        count++;
        j++;
    }

will never run more than visited.length times total.

The outer loop is, of course, O(n). So, you get

outer loop: O(n)
+ inner loop: O(n) when summed over all iterations of the outer loop
= O(n)

Upvotes: 1

Related Questions