Talk:Hash table: Difference between revisions
Jump to navigation
Jump to search
imported>Alexander Wiebel No edit summary |
imported>Nick Johnson No edit summary |
||
| Line 2: | Line 2: | ||
: 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) | ::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) | ||
:::I was hoping to come in later and write the article 'Big O Notation,' which would have cleared this up. As a general style rule, should I explain that in the article text instead of just linking to Big O Notation? --[[User:Nick Johnson|Nick Johnson]] 15:57, 21 February 2007 (CST) | |||
Revision as of 16:57, 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)
- I was hoping to come in later and write the article 'Big O Notation,' which would have cleared this up. As a general style rule, should I explain that in the article text instead of just linking to Big O Notation? --Nick Johnson 15:57, 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)