Coding since 11yo, that makes it over 30 years now ~~~
Have a PhD in Comp Sci ~~~
Love to go on bike tours ~~~
I try to stay as generalist as I can in this crazy wide place coding is at now.
You're right, space is part of the equation too. It's all about what tradeoffs you're happy to make.
In this case, we're checking for duplicates in the string so we're either storing a memo hash (O(n) on space) or iterating over the pairs of elements (O(n^2) on time).
This one is O(n) on space and time, but you could defn make a fn that was O(1) on space if you were ok with O(n^2) on time.
(O(n) == O(2n) btw. The notation includes a multiplier to cover differences in the base case. So the top function up there where [...s] implicitly loops through the string before even hitting the every, actually has the same complexity as the lower function that is genuinely just one loop.)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
It's always nice to avoid a second iteration
We also have space complexity
You're right, space is part of the equation too. It's all about what tradeoffs you're happy to make.
In this case, we're checking for duplicates in the string so we're either storing a memo hash (O(n) on space) or iterating over the pairs of elements (O(n^2) on time).
This one is O(n) on space and time, but you could defn make a fn that was O(1) on space if you were ok with O(n^2) on time.
(O(n) == O(2n) btw. The notation includes a multiplier to cover differences in the base case. So the top function up there where
[...s]
implicitly loops through the string before even hitting theevery
, actually has the same complexity as the lower function that is genuinely just one loop.)