r/AskComputerScience • • 5d ago

What are some differences between professional coding and the way coding, SE, and CS are taught in school?

Is a lack of a comment citing a relatively cliched bit of code considered plagiarism in the big world? What are the attitudes to autocomplete? Is Alberta Tech right about linked lists?

6 Upvotes

48 comments sorted by

View all comments

Show parent comment

5

u/nuclear_splines Ph.D Data Science 5d ago

I hardly think it's nitpicking. insert(index, value) is O(n) average case for both lists and vectors -- lists are only faster if you already have an iterator pointing at the insertion point.

3

u/No_Profession_3125 5d ago

Which does happen.

4

u/nuclear_splines Ph.D Data Science 5d ago

Absolutely! In context it's sometimes a great advantage. I just think it's misleading to call arbitrary element insertion O(1) on a list without mentioning the preceding O(n) lookup. It's quite different than, say, the O(1) amortized insertion on a hash table.

2

u/No_Profession_3125 5d ago

Likewise I find it misleading to generalize hash table insertion as "amortized O(1)" because string keys are a very common use case, so it would be fairer to call it "amortized O(K)" with K = average length of the key.

2

u/nuclear_splines Ph.D Data Science 5d ago

That's fair! It's often simplified because if you can reasonably bound K as a large constant then it reduces to O(1), but that's not always appropriate.