O(1) or O(N)

  • Thread starter Thread starter Boris
  • Start date Start date
B

Boris

What is big-O of

1) System.Collection.ArrayList.Count
2) System.Collection.ArrayList.Queue

Is it O(1) or O(N)? I was not able to find the answer on MSDN or anywhere
else.

thanks,
-Boris
 
Boris,

For the Count property of the ArrayList, it is O(1). I assume you want
to know what it is for the Count proerty on the Queue class as well. I
assume it is O(1) as well.

Hope this helps.
 
Boris said:
What is big-O of

1) System.Collection.ArrayList.Count
2) System.Collection.ArrayList.Queue

Is it O(1) or O(N)? I was not able to find the answer on MSDN or anywhere
else.
Click to expand...

Please see my reply to the same question you posted last week.
 
Thanks for your reply. For some reason I couldn't find my message from
last week.

Do you know if there exists a reference manual for .Net Framework Class
Library which lists big-O of each framework class method?

Thanks,

-Boris
 
Boris said:
Thanks for your reply. For some reason I couldn't find my message from
last week.

Do you know if there exists a reference manual for .Net Framework Class
Library which lists big-O of each framework class method?
Click to expand...

I don't know of any such manual - and it would have to be specific to a
particular version, as the implementation could change between
versions.
 
Boris said:
How were you able to access this information?
Click to expand...

Well, the implementation of ArrayList.Size is pretty obvious - given
that there's a buffer and a count, all it's got to do is return that
count.

As for Queue - well, a few tests didn't show it being bad, and it makes
sense for it to be a member just like in ArrayList. You could always
use reflector to check, of course - but that would be a licence
violation...
 
MS releated the CLI source code a while back so you can check that to have
an idea how it is implemented. Like a previous post said, new versions may
result to changes in the source code so it's more of just a reference. I
have a copy of the SSCLI dated 11/1/2002 and it is indeed O(1) for both
Count methods.

Eric


--
Eric Cherng
MCP, MCDBA, MCSD
http://echerng.com
 
Back
Top