{"revision": {"id": "f3a68446-2f95-11f1-87d6-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\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 80 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 = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( numbers )\r\n\r\n while lo < hi:\r\n\r\n     mid = int( (lo + hi) / 2 )\r\n\r\n     if needle > numbers[ mid ]:\r\n         lo = mid + 1\r\n     elif needle < numbers[ mid ]:\r\n         hi = mid\r\n     else:\r\n         print \"found %d which is the %d index of the list\" % ( numbers[ mid ], mid )\r\n         break\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\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways 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\n", "source_format": "rst", "revision_number": 18, "created": 1315868864000}}