1

I'm looking for Big O notation - avereage , for only the access of one element. Here is what I have so far. Once again that is Big O, Average, Access. Actually I only need it for a Searchable Red and Black Tree and a simple Modulus Hash.

Arrays - O(1) Linked Lists - O(X) Trees(defined above) - ? Hashes(defined above) - ?

enter image description here

  • Is this no Language Independent? Why is it tagged C++? – Alok Save Oct 14 '11 at 17:34
  • 3
    Honestly, get your hands on a copy of this book: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1318613724&sr=8-1. It can answer every question you'd ever have on common algorithms, including this one. – riwalk Oct 14 '11 at 17:36

1 Answers1

2

Tree = O(log n)

Hashtable = O(1)

DeCaf
  • 6,026
  • 1
  • 29
  • 51
  • For tree that log is base 2? Hash makes sense –  Oct 14 '11 at 17:37
  • 2
    @ChrisAaker: The base in the `log` does not matter since all log functions are the same to a multiplicative constant, and the multiplicative constant is masked by the big-Oh. – NPE Oct 14 '11 at 17:39
  • the base is irrelevant. log(2) n = ln n / ln 2. same for any base -- you're dividing by a constant. – cHao Oct 14 '11 at 17:41
  • I don't think your reasoning is wrong, but the big-Oh notation does not consider these constants. For example it doesn't matter if a linear algorithm traverses a list once, twice or 100 times, the complexity would still be O(n). Read a good post about it here: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – DeCaf Oct 14 '11 at 17:54
  • Yes, it is for a balanced binary tree since each traversal between nodes cuts the remaining nodes to check in half. But it is still not relevant for big-o notation. – DeCaf Oct 15 '11 at 18:51