Hi Saloni,
In the algorithm I used above, the reason its time complexity is O(n^2) can be found by looking at the for loop. The for loop examines each element of s, which takes O(n) time (n being the length of s). Then, inside the for loop, I call expandAroundCenter. In expandAroundCenter, I'm again traversing the string (even though I may just be looking at one character, I could be looking at the entire string again, like in the case of checking the "B" in "ABA"). That would take, at most, O(n) time. Because expandAroundCenter is nested inside the for loop, that means it takes a total of O(n^2) time.
In your function, you have a while loop, which goes from the end of the string to the start. In other words, you could write while (len>0) {... as for (let i = len; i > 0; i--) {. So in that line, that's O(n). Then inside the loop, you have another for loop. If you think about the example of "AAAA", the first time through the while loop, len would = 4, and inside the for loop, str would = "AAAA". Then, isPalindrom would be called, and it'd start at either end, and end up checking every character of the string, which is also O(n). So, it looks like overall the time would be O(n^2).
I am a believer of the Root Cause Analysis. Ask "How, What, Why" until you can dissect it with no further to go. Well, I am a frontend developer ready for new challenges!
Hi Saloni,
In the algorithm I used above, the reason its time complexity is O(n^2) can be found by looking at the for loop. The for loop examines each element of
s, which takes O(n) time (n being the length ofs). Then, inside the for loop, I callexpandAroundCenter. InexpandAroundCenter, I'm again traversing the string (even though I may just be looking at one character, I could be looking at the entire string again, like in the case of checking the "B" in "ABA"). That would take, at most, O(n) time. Because expandAroundCenter is nested inside the for loop, that means it takes a total of O(n^2) time.In your function, you have a while loop, which goes from the end of the string to the start. In other words, you could write
while (len>0) {...asfor (let i = len; i > 0; i--) {. So in that line, that's O(n). Then inside the loop, you have another for loop. If you think about the example of "AAAA", the first time through the while loop, len would = 4, and inside the for loop, str would = "AAAA". Then,isPalindromwould be called, and it'd start at either end, and end up checking every character of the string, which is also O(n). So, it looks like overall the time would be O(n^2).Thank you for the help with time complexity Alisa! Also, your post is very well explained. So thank you for that as well :)