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

Question

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;

whta is the purpose of it? do you have some data and result? — Nina Scholz
– Nina Scholz, Commented Dec 20, 2021 at 17:59
@NinaScholz its just a hacker rank question I solved so I'm trying to figure out time and space complexity for interview prep — Anas
– Anas, Commented Dec 20, 2021 at 18:04
@user1599011 it can run for the length of s because s can have the same letter for the whole string — Anas
– Anas, Commented Dec 20, 2021 at 18:06

CertainPerformance · Accepted Answer · 2021-12-20 18:05:14Z

1

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)

answered Dec 20, 2021 at 18:05

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

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

3 Comments

Anas Over a year ago

but j gets incremented each time so it can run for the whole length of s if s[j] === s[i] is always true

CertainPerformance Over a year ago

If it runs for the whole length the first time - when i is 0 - then it won't run for any of the other is. Over the entire function call, the while loop will, in total, run no more than s.length times.

Anas Over a year ago

ahh that makes a lot of sense.. no wonder my algorithm ran pretty fast even though s could've been as large as 100k. THANK YOU!

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related