Talk:Hash table: Difference between revisions
Jump to navigation
Jump to search
imported>Alexander Wiebel (O(n) explanation) |
imported>Alexander Wiebel No edit summary |
||
| Line 1: | Line 1: | ||
may I ask what is O(1)? [[User:Robert Tito|Robert Tito]] | [[User talk:Robert Tito|Talk]] 14:39, 21 February 2007 (CST) | may I ask what is O(1)? [[User:Robert Tito|Robert Tito]] | [[User talk:Robert Tito|Talk]] 14:39, 21 February 2007 (CST) | ||
: The ''O(n)''-notation gives a hint on the complexity of a task, i.e. on the computational time needed to perform the task. n is the number of elements in consideration. This means if a task is in O(n) class, the time to perform the task increases linearly with the number of elements. O(1) (what you asked for) means that the time does not increase with the number of elements. O(n^2) would mean that time grows quadratically with the number of elements. Typical classe are O(1), O(log n), O(n), O(n log n), O(n2) and O(2^n). -- [[User:Alexander Wiebel|Alexander Wiebel]] 15:08, 21 February 2007 (CST) | : The ''O(n)''-notation gives a hint on the complexity of a task, i.e. on the computational time needed to perform the task. n is the number of elements in consideration. This means if a task is in O(n) class, the time to perform the task increases linearly with the number of elements. O(1) (what you asked for) means that the time does not increase with the number of elements. O(n^2) would mean that time grows quadratically with the number of elements. Typical classe are O(1), O(log n), O(n), O(n log n), O(n2) and O(2^n). -- [[User:Alexander Wiebel|Alexander Wiebel]] 15:08, 21 February 2007 (CST) | ||
::By the way, this belongs to the field of theoretical computer science. Hope that helps. -- [[User:Alexander Wiebel|Alexander Wiebel]] 15:10, 21 February 2007 (CST) | |||
Revision as of 15:10, 21 February 2007
may I ask what is O(1)? Robert Tito | Talk 14:39, 21 February 2007 (CST)
- The O(n)-notation gives a hint on the complexity of a task, i.e. on the computational time needed to perform the task. n is the number of elements in consideration. This means if a task is in O(n) class, the time to perform the task increases linearly with the number of elements. O(1) (what you asked for) means that the time does not increase with the number of elements. O(n^2) would mean that time grows quadratically with the number of elements. Typical classe are O(1), O(log n), O(n), O(n log n), O(n2) and O(2^n). -- Alexander Wiebel 15:08, 21 February 2007 (CST)
- By the way, this belongs to the field of theoretical computer science. Hope that helps. -- Alexander Wiebel 15:10, 21 February 2007 (CST)