Search data structure: Difference between revisions

Revision as of 15:47, 13 February 2010

Revision as of 22:15, 14 February 2010

Line 25:

====Asymptotic worst-case analysis====

In this table, the [[big-O notation|notation O(''f''(''n'')]] means "proportionalnot toexceeding some fixed multiple of ''f''(''n'')" in the worst case".

{| class="wikitable"

Line 36:

! Space usage

|-

| Unsorted [[Array data structure|Arrayarray]]

| [[LinearConstant time|O(n1)]]

| O(1)
| [[Linear time|O(''n'')]]

| O(''n'')

| [[Linear time|O(n)]] or [[Constant time|O(1)]]<ref>if indexed by value - see [[control table]],"trivial hash function" example</ref>

| [[Linear time|O(n)]] or [[Constant time|O(1)]]<ref>if indexed by value - see [[control table]],"trivial hash function" example</ref>

| O(n)

|-

| Value-indexed array

| O(1)

| O(1)

| O(1)

| O(''n'')

| O(''n'')

|-

| Sorted Array

| [[Linear time|O(''n'')]]

| [[Linear time|O(''n'')]]

| [[Logarithmic time|O(log ''n'')]]

| [[Constant time|O(1)]]

| O(''n'')

|-

| Unsorted [[Linked list]]

| [[Constant time|O(1)]]

| [[Constant time|O(1)]]

| [[Linear time|O(''n'')]]

| [[Linear time|O(''n'')]]

| O(''n'')

|-

| Sorted linked list

| [[Linear time|O(''n'')]]

| [[Linear time|O(''n'')]]

| [[Linear time|O(''n'')]]

| [[Constant time|O(1)]]

| O(''n'')

|-

| [[Self-balancing binary tree]]

| [[Logarithm|O(log ''n'')]]

| [[Logarithm|O(log ''n'')]]

| [[Logarithm|O(log ''n'')]]

| [[Logarithm|O(log ''n'')]]

| O(n)

|-

| [[Heap (data structure)|Heap]]

| [[Logarithm|O(log ''n'')]]

| O(log ''n'')<ref>CanFor onlymin delete theor max; O(or''n'') minfor ingeneral a min heap)element.</ref>

| [[Linear time|O(''n'')]]

| [[Constant time|O(1)]]

| O(''n'')

|-

| [[Hash table]]

| [[Constant time|O(1)]]

| [[Constant time|O(1)]])

| [[Constant time|O(1)]]

| O(''n'')

| [[Linear time|O(n)]] or [[O(1)]]<ref>if "trivial hash function" possible</ref>

| O(''n'')

|}

This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs.

== Footnotes ==