ComputationalComplexity.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[45,\n",
       " 19,\n",
       " 44,\n",
       " 12,\n",
       " 63,\n",
       " 27,\n",
       " 1,\n",
       " 35,\n",
       " 56,\n",
       " 40,\n",
       " 59,\n",
       " 78,\n",
       " 97,\n",
       " 28,\n",
       " 51,\n",
       " 90,\n",
       " 77,\n",
       " 34,\n",
       " 50,\n",
       " 29,\n",
       " 10,\n",
       " 76,\n",
       " 9,\n",
       " 15,\n",
       " 16,\n",
       " 69,\n",
       " 67,\n",
       " 42,\n",
       " 64,\n",
       " 54,\n",
       " 6,\n",
       " 83,\n",
       " 61,\n",
       " 53,\n",
       " 49,\n",
       " 39,\n",
       " 99,\n",
       " 55,\n",
       " 48,\n",
       " 41,\n",
       " 75,\n",
       " 66,\n",
       " 24,\n",
       " 5,\n",
       " 30,\n",
       " 26,\n",
       " 92,\n",
       " 14,\n",
       " 89,\n",
       " 73,\n",
       " 7,\n",
       " 2,\n",
       " 65,\n",
       " 91,\n",
       " 84,\n",
       " 98,\n",
       " 60,\n",
       " 93,\n",
       " 62,\n",
       " 95,\n",
       " 87,\n",
       " 0,\n",
       " 22,\n",
       " 80,\n",
       " 79,\n",
       " 71,\n",
       " 70,\n",
       " 25,\n",
       " 68,\n",
       " 85,\n",
       " 4,\n",
       " 31,\n",
       " 11,\n",
       " 23,\n",
       " 52,\n",
       " 72,\n",
       " 96,\n",
       " 33,\n",
       " 43,\n",
       " 47,\n",
       " 36,\n",
       " 18,\n",
       " 20,\n",
       " 3,\n",
       " 58,\n",
       " 86,\n",
       " 82,\n",
       " 8,\n",
       " 21,\n",
       " 88,\n",
       " 13,\n",
       " 17,\n",
       " 57,\n",
       " 74,\n",
       " 46,\n",
       " 81,\n",
       " 38,\n",
       " 32,\n",
       " 94,\n",
       " 37]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "\n",
    "l = list(range(100))\n",
    "random.shuffle(l)\n",
    "\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found\n"
     ]
    }
   ],
   "source": [
    "# search for an elemnt q in the list: O(n) where n is the length of the list\n",
    "q = 31\n",
    "isFound=False;\n",
    "for ele in l:\n",
    "    if ele==31:\n",
    "        print(\"Found\")\n",
    "        isFound=True\n",
    "        break;\n",
    "if isFound == False:\n",
    "    print(\"Not Found\")\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "31"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#What if the list is sorted? Can we search faster?\n",
    "# Show O(log n)\n",
    "\n",
    "import math\n",
    "\n",
    "#Source: http://www.geeksforgeeks.org/binary-search/ \n",
    "#Returns index of x in arr if present, else -1\n",
    "def binarySearch (arr, l, r, x):\n",
    " \n",
    "    # Check base case\n",
    "    if r >= l:\n",
    " \n",
    "        mid = l + math.floor((r - l)/2)\n",
    " \n",
    "        # If element is present at the middle itself\n",
    "        if arr[mid] == x:\n",
    "            return mid\n",
    "         \n",
    "        # If element is smaller than mid, then it can only\n",
    "        # be present in left subarray\n",
    "        elif arr[mid] > x:\n",
    "            return binarySearch(arr, l, mid-1, x)\n",
    " \n",
    "        # Else the element can only be present in right subarray\n",
    "        else:\n",
    "            return binarySearch(arr, mid+1, r, x)\n",
    " \n",
    "    else:\n",
    "        # Element is not present in the array\n",
    "        return -1\n",
    "\n",
    "\n",
    "l.sort();\n",
    "arr = l;\n",
    "q =31;\n",
    "binarySearch(arr,0,len(arr)-1,q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "43\n",
      "44\n",
      "46\n",
      "38\n",
      "47\n",
      "35\n",
      "45\n",
      "36\n",
      "34\n",
      "41\n",
      "4\n",
      "28\n",
      "18\n",
      "19\n",
      "40\n",
      "29\n",
      "12\n",
      "7\n",
      "33\n",
      "23\n",
      "1\n",
      "30\n",
      "42\n",
      "20\n",
      "8\n",
      "6\n",
      "24\n",
      "22\n",
      "14\n",
      "27\n",
      "48\n",
      "26\n",
      "13\n",
      "39\n",
      "17\n",
      "11\n",
      "0\n",
      "25\n",
      "37\n",
      "10\n",
      "49\n",
      "2\n",
      "9\n",
      "31\n",
      "21\n",
      "32\n",
      "16\n",
      "3\n",
      "5\n",
      "15\n",
      "Number of common elements: 50\n"
     ]
    }
   ],
   "source": [
    "# Find elements common in two lists:\n",
    "l1 = list(range(100))\n",
    "random.shuffle(l1)\n",
    "\n",
    "\n",
    "l2 = list(range(50))\n",
    "random.shuffle(l2)\n",
    "\n",
    "# find common elements : O(n*m)\n",
    "cnt=0;\n",
    "for i in l1:\n",
    "    for j in l2:\n",
    "        if i==j:\n",
    "            print(i)\n",
    "            cnt += 1;\n",
    "print(\"Number of common elements:\", cnt)                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n",
      "44\n",
      "17\n",
      "30\n",
      "23\n",
      "2\n",
      "15\n",
      "37\n",
      "24\n",
      "29\n",
      "45\n",
      "10\n",
      "32\n",
      "7\n",
      "19\n",
      "36\n",
      "47\n",
      "14\n",
      "41\n",
      "16\n",
      "5\n",
      "42\n",
      "34\n",
      "33\n",
      "39\n",
      "0\n",
      "31\n",
      "1\n",
      "27\n",
      "35\n",
      "22\n",
      "8\n",
      "46\n",
      "20\n",
      "18\n",
      "13\n",
      "25\n",
      "3\n",
      "26\n",
      "12\n",
      "40\n",
      "49\n",
      "4\n",
      "6\n",
      "11\n",
      "9\n",
      "38\n",
      "28\n",
      "48\n",
      "43\n",
      "Number of common elements: 50\n"
     ]
    }
   ],
   "source": [
    "# Find elements common in two lists:\n",
    "l1 = list(range(100))\n",
    "random.shuffle(l1)\n",
    "\n",
    "\n",
    "l2 = list(range(50))\n",
    "random.shuffle(l2)\n",
    "\n",
    "# find common elemnts in lists in O(n) time and O(m) space if m<n\n",
    "\n",
    "## add all elements in the smallest list into a hashtable/Dict: O(m) space\n",
    "smallList = {}\n",
    "for ele in l2:\n",
    "    smallList[ele] = 1; # any value is OK. Key is important\n",
    "    \n",
    "# Now find common element \n",
    "cnt=0;\n",
    "for i in l1:\n",
    "    if smallList.get(i) != None: # search happens in constant time.\n",
    "        print(i);\n",
    "        cnt += 1;\n",
    "print(\"Number of common elements:\", cnt)                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}