tag:blogger.com,1999:blog-38888296.post1809352020739629051..comments2022-05-19T01:07:28.063+08:00Comments on C# Snippets: Runtime Complexity of .NET Generic CollectionJeow Li Huanhttp://www.blogger.com/profile/11871374011115309096noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-38888296.post-57519964151901723222022-05-18T22:02:15.216+08:002022-05-18T22:02:15.216+08:00HashSet .Contains() exists and I believe it has a ...<i>HashSet .Contains()</i> exists and I believe it has a <b>O(1)</b> complexity. <br />Found it: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.contains?view=net-6.0Alexnoreply@blogger.comtag:blogger.com,1999:blog-38888296.post-59522389449756148032018-05-08T18:39:15.273+08:002018-05-08T18:39:15.273+08:00@Alisson Reinaldo Silva: because for SortedList, t...@Alisson Reinaldo Silva: because for SortedList, the indexer is not retrieving by index, but by key. It does a binary search to look for the key in the array.Jeow Li Huanhttps://www.blogger.com/profile/11871374011115309096noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-67932684627558927872018-05-08T10:17:11.285+08:002018-05-08T10:17:11.285+08:00I don't understend why a SortedList has O(log ...I don't understend why a SortedList has O(log n) time complexity when getting an item by its index. The only drawback of them is adding and removing items (because we have to keep the sort), other than that, accessing items by index should have the same time complexity of List, for example.Anonymoushttps://www.blogger.com/profile/02288662926171580107noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-2547188317929556582016-07-27T20:02:29.964+08:002016-07-27T20:02:29.964+08:00@Roberto: turns out it's so hard to name the h...@Roberto: turns out it's so hard to name the heading. The Find only applies to LinkedList, but turns out that I shouldn't put that in the same column as Item[i]. I've changed the last column MoveNext to finding a value, which would require you to enumerate through the entire collection in the general caseJeow Li Huanhttps://www.blogger.com/profile/11871374011115309096noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-90834758970057539062016-07-27T19:42:06.067+08:002016-07-27T19:42:06.067+08:00Sorry: I forgot to say which method! I was speakin...Sorry: I forgot to say which method! I was speaking about List.Find<br />https://msdn.microsoft.com/en-us/library/x0b5b5bc.aspxRobertonoreply@blogger.comtag:blogger.com,1999:blog-38888296.post-31228981401960148112016-07-27T19:13:27.557+08:002016-07-27T19:13:27.557+08:00@Roberto: MSDN stated that the IndexOf and Contain...@Roberto: MSDN stated that the IndexOf and Contains operations to be O(n). I'm missing those methods in my table...<br /><br />Let me add themJeow Li Huanhttps://www.blogger.com/profile/11871374011115309096noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-85666812802212007572016-07-27T18:33:00.199+08:002016-07-27T18:33:00.199+08:00MSDN about List says: "This method performs a...MSDN about List says: "This method performs a linear search; therefore, this method is an O(n) operation, where n is Count."<br /><br />In your table is O(1).<br /><br />Did I misunderstood?Robertonoreply@blogger.comtag:blogger.com,1999:blog-38888296.post-56670271419603036502016-06-07T18:07:06.388+08:002016-06-07T18:07:06.388+08:00it’s ok to show some appreciation and say ‘great p...it’s ok to show some appreciation and say ‘great post’<br /><a href="http://www.stackoverflow.info/search/label/ASP.NET" rel="nofollow">Asp .NET developer</a>Anonymoushttps://www.blogger.com/profile/00962069622504243950noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-56955738764726528612015-11-17T11:28:52.288+08:002015-11-17T11:28:52.288+08:00A million dollar worth entry!.A million dollar worth entry!.Naresh Singh Dhamihttps://www.blogger.com/profile/03918696121362398856noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-8731730870127887422015-04-30T22:39:04.313+08:002015-04-30T22:39:04.313+08:00Still super useful, 5 years later.Still super useful, 5 years later.Charleshttps://www.blogger.com/profile/13394114739678591400noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-15728789556775059972015-03-24T03:49:23.344+08:002015-03-24T03:49:23.344+08:00Would be worth add the .NET4 Concurrent Collection...Would be worth add the .NET4 Concurrent Collections to this table!Chris Marisichttps://www.blogger.com/profile/08904925342941324684noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-88699732787573714932012-06-06T21:53:03.510+08:002012-06-06T21:53:03.510+08:00You don't know index of item in SortedList, so...You don't know index of item in SortedList, so you take Item by Key. If you want take Item by Index, you need<br />1) int IndexOfKey(TKey key);<br />2) TValue GetByIndex(int index);<br />And it's same O(log n) in sum :)Shuhttps://www.blogger.com/profile/16919979920294046991noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-7293035345494916842012-06-06T21:43:17.455+08:002012-06-06T21:43:17.455+08:00Yes, the array. But when trying to get the Item, i...Yes, the array. But when trying to get the Item, is a binary search inside <i>TValue this[TKey key] {get}</i> = <i>O(log n)</i>Shuhttps://www.blogger.com/profile/16919979920294046991noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-76501234656571577282012-06-06T21:29:30.429+08:002012-06-06T21:29:30.429+08:00Thanks Shuisky. Added Find(i) to the heading.
Why ...Thanks Shuisky. Added Find(i) to the heading.<br />Why do you say SortedList Item[i] = O(log n)? Internally it's an Array, so shouldn't access be instantaneous?Jeow Li Huanhttps://www.blogger.com/profile/11871374011115309096noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-88761134547326887952012-05-05T15:28:16.816+08:002012-05-05T15:28:16.816+08:00Big THANK YOU, for this table!
I think you have t...Big THANK YOU, for this table!<br /><br />I think you have two mistakes:<br />1. LinkedList haven't Item[i], it has Find(T) = O(n)<br />2. SortedList Item[i] = O(log n)Shuhttps://www.blogger.com/profile/16919979920294046991noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-69512320959256658782011-12-08T13:31:37.290+08:002011-12-08T13:31:37.290+08:00Thanks! MSDN did for some of the structures, but I...Thanks! MSDN did for some of the structures, but I did find that the SortedDictionary complexity that they stated is wrong... I guess wrong documentation is worse than no documentation, that is why MSDN didn't want to document it.Jeow Li Huanhttps://www.blogger.com/profile/11871374011115309096noreply@blogger.comtag:blogger.com,1999:blog-38888296.post-38834610758753994422011-11-29T04:23:23.802+08:002011-11-29T04:23:23.802+08:00Nice work, very useful.
MSDN should display these...Nice work, very useful.<br /><br />MSDN should display these information for every data structures they provide.Anonymousnoreply@blogger.com