Search data structure: Difference between revisions

Revision as of 18:32, 5 October 2013

Revision as of 18:43, 5 October 2013

Line 34:

! Insert

! Delete

! Get at index

! Search

! Find maximum/minimum

! Space usage

|-

| Unsorted [[Array data structure|array]]

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

| O(1)

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

| O(''n'')

| O(''n'')

|-

| Value-indexed array

| O(1)

| O(1)

| O(1)

| O(''n'')

| O(''n'')

| O(''n'')

Line 55 ⟶ 50:

| O(''n'')

| O(''n'')

| O(1)

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

| O(log ''n'')

| O(1)

| O(''n'')

Line 62 ⟶ 58:

| O(1)^*

| O(1)^*

| O(1''n'')

| O(''n'')

| O(''n'')

Line 70 ⟶ 67:

| O(1)^*

| O(''n'')

| O(1''n'')

| O(1''n'')

| O(''n'')

|-

Line 76 ⟶ 74:

| O(log ''n'')

| O(log ''n'')

| N/A

| O(log ''n'')

| O(log ''n'')

Line 83 ⟶ 82:

| O(log ''n'')

| O(log ''n'')^**

| N/A

| O(''n'')

| O(1)

Line 90:

| O(1)

| O(1)

| N/A

| O(1)

| O(''n'')