lundi 7 janvier 2019

Interview Complexity Question: If statement and comparison complexity

I was studying some interview questions and came across this problem right here. Question Image

I understood everything for the most part except the part that I have boxed in red. If every string within the array has been sorted. Then shouldn't sorting the array take only O(a log a)? Why did they multiply that by O(s)? It explains that the string comparison when sorting would take O(s), with s being the largest string size. That makes sense... However, I assumed the comparison would look something like this...

if ( array[x].equals(array[y]) ) {...}

Don't if statements take a complexity of O(1)? So shouldn't that be disregarded? I might be wrong but i think i had read that executing if statements and any other imbedded statement (Not Loop) would take a complexity of O(1). Please correct me if I am wrong and enlighten me on how to calculate complexity properly.

Aucun commentaire:

Enregistrer un commentaire