n keys, and assume strongly connected | cscareers.dev | Page 1

dreamy axle Dec 18, 2023, 2:26 AM

#

so it's n^2 because for each key you could have n nodes in that node's values?

worthy fern Dec 18, 2023, 2:26 AM

#

assuming every node is connected to every other node

#

in that case ur adj list is kinda useless

dreamy axle Dec 18, 2023, 2:28 AM

#

yeah

worthy fern Dec 18, 2023, 2:28 AM

#

bc in a matrix at least u can just check if the value is set

#

and that would be O(1)

#

assuming u initialized NxN grid

#

wait im confusing

#

time with space again sry

#

but yeah point still stands

dreamy axle Dec 18, 2023, 2:29 AM

#

yeah that makes sense

#

but in any case when you have a hashmap that has n keys and the value for each key could be an array up to n nodes, the Space would be n^2 right?

worthy fern Dec 18, 2023, 2:30 AM

#

yeah

dreamy axle Dec 18, 2023, 2:30 AM

#

ty

worthy fern Dec 18, 2023, 2:30 AM

#

n keys with n values each

dreamy axle Dec 18, 2023, 3:12 AM

#

hey, anoter quick question about space if that's okay. if I slice a string str[:i] but immediatley convert it to an int(str[i;]) is this adding to space complexity? if nothing else was stored, would the slice still result in a O(n) overall SC where n is len of str

#n keys, and assume strongly connected