Search data structure: Difference between revisions

Revision as of 22:17, 14 February 2010

Revision as of 22:24, 14 February 2010

Line 25:

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

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

{| class="wikitable"

Line 80:

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

| O(log ''n'')

| O(log ''n'')<refsup>For min or max; O(''n'') for general element.†</refsup>

| O(''n'')

| O(1)

Line 91:

| O(''n'')

| O(''n'')

|}<small>&nbsp;† The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>

|}

This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.

== Footnotes ==