{"revision": {"id": "f3a66bf4-2f95-11f1-a315-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Always look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n    if number > max:\r\n        max = number\r\n\r\n**The Big-0 of this program is n  O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n     if number == 0:\r\n         return True\r\n\r\n**The Big-0 of this program is n  O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n     m = int( i + j / 2 )\r\n     if needle < numbers[ m ]:\r\n         i = m + 1\r\n     else:\r\n         j = m\r\n\r\n if needle == m:\r\n     print True\r\n\r\n\r\n* Worst case in  8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n  Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){   }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 13, "created": 1315857505000}}