time_complexity.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNF/7/aXVx+OEq2XHCI8PSK",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/regain001/Interview-Preparation/blob/master/time_complexity.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( 1 )**\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "lOhA6oIWBtub"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Array\n",
        "nums = [1, 2, 3]\n",
        "nums.append(4)    # push to end\n",
        "nums.pop()        # pop from end\n",
        "nums[0]           # lookup\n",
        "nums[1]\n",
        "nums[2]\n",
        "\n",
        "# HashMap / Set\n",
        "hashMap = {}\n",
        "hashMap[\"key\"] = 10     # insert\n",
        "print(\"key\" in hashMap) # lookup\n",
        "print(hashMap[\"key\"])   # lookup\n",
        "hashMap.pop(\"key\")      # remove "
      ],
      "metadata": {
        "id": "6Xm1f6jlCpJZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( n )**\n",
        "\n",
        "\n",
        "---\n"
      ],
      "metadata": {
        "id": "6tIEG_NECXMJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "nums = [1, 2, 3]\n",
        "sum(nums)           # sum of array\n",
        "for n in nums:      # looping\n",
        "    print(n)\n",
        "\n",
        "nums.insert(1, 100) # insert middle\n",
        "nums.remove(100)    # remove middle\n",
        "print(100 in nums)  # search\n",
        "\n",
        "import heapq\n",
        "heapq.heapify(nums) # build heap\n",
        "\n",
        "# sometimes even nested loops can be O(n)\n",
        "# (e.g. monotonic stack or sliding window)"
      ],
      "metadata": {
        "id": "yn47f-f9CtxB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( n^2 )**\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ],
      "metadata": {
        "id": "1sfrxK-WCu2R"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Traverse a square grid\n",
        "nums = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
        "for i in range(len(nums)):\n",
        "    for j in range(len(nums[i])): \n",
        "        print(nums[i][j])\n",
        "\n",
        "\n",
        "# Get every pair of elements in array\n",
        "nums = [1, 2, 3]\n",
        "for i in range(len(nums)):\n",
        "    for j in range(i + 1, len(nums)):\n",
        "        print(nums[i], nums[j])\n",
        "\n",
        "# Insertion sort (insert in middle n times -> n^2)"
      ],
      "metadata": {
        "id": "f5t3KxQhC1IJ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( n * m )**\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ],
      "metadata": {
        "id": "oaD5b440C-m4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Get every pair of elements from two arrays\n",
        "nums1, nums2 = [1, 2, 3], [4, 5]\n",
        "for i in range(len(nums1)):\n",
        "    for j in range(len(nums2)):\n",
        "        print(nums1[i], nums2[j])\n",
        "\n",
        "# Traverse rectangle grid\n",
        "nums = [[1, 2, 3], [4, 5, 6]]\n",
        "for i in range(len(nums)):\n",
        "    for j in range(len(nums[i])):\n",
        "        print(nums[i][j])"
      ],
      "metadata": {
        "id": "bwgIXPgaDGJY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( n^3 )**\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ],
      "metadata": {
        "id": "yEi24AD-DKlh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Get every triplet of elements in array\n",
        "nums = [1, 2, 3]\n",
        "for i in range(len(nums)):\n",
        "    for j in range(i + 1, len(nums)):\n",
        "        for k in range(j + 1, len(nums)):\n",
        "            print(nums[i], nums[j], nums[k])"
      ],
      "metadata": {
        "id": "01NyJLh-DTFp"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( logn )**\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "GQ3TpyEoDaTo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Binary search\n",
        "nums = [1, 2, 3, 4, 5]\n",
        "target = 6\n",
        "l, r = 0, len(nums) - 1\n",
        "while l <= r:\n",
        "    m = (l + r) // 2\n",
        "    if target < nums[m]:\n",
        "        r = m - 1\n",
        "    elif target > nums[m]:\n",
        "        l = m + 1\n",
        "    else:\n",
        "        print(m)\n",
        "        break\n",
        "\n",
        "# Binary Search on BST\n",
        "def search(root, target):\n",
        "    if not root:\n",
        "        return False\n",
        "    if target < root.val:\n",
        "        return search(root.left, target)\n",
        "    elif target > root.val:\n",
        "        return search(root.right, target)\n",
        "    else: \n",
        "        return True\n",
        "\n",
        "# Heap Push and Pop\n",
        "import heapq\n",
        "minHeap = []\n",
        "heapq.heappush(minHeap, 5)\n",
        "heapq.heappop(minHeap)"
      ],
      "metadata": {
        "id": "hE6Q2xHKDfhg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( nlogn )**\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "fQBmgza4DrBY"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# HeapSort\n",
        "import heapq\n",
        "nums = [1, 2, 3, 4, 5]\n",
        "heapq.heapify(nums)     # O(n)\n",
        "while nums:\n",
        "    heapq.heappop(nums) # O(logn)\n",
        "\n",
        "# MergeSort (and most built-in sorting functions)"
      ],
      "metadata": {
        "id": "31m12yzFDspw"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( 2^n )**\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ],
      "metadata": {
        "id": "NcDX4XRLDvsh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Recursion, tree height n, two branches\n",
        "def recursion(i, nums):\n",
        "    if i == len(nums):\n",
        "        return 0\n",
        "    branch1 = recursion(i + 1, nums)\n",
        "    branch2 = recursion(i + 2, nums)"
      ],
      "metadata": {
        "id": "cMTe3vZFEV_R"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( c^n )**\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "eukLRqu-EXMI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# c branches, where c is sometimes n.\n",
        "def recursion(i, nums, c):\n",
        "    if i == len(nums):\n",
        "        return 0\n",
        "    \n",
        "    for j in range(i, i + c):\n",
        "        branch = recursion(j + 1, nums)"
      ],
      "metadata": {
        "id": "9z7ir-UYEbRB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( sqrt(n) )**\n",
        "\n",
        "\n",
        "---\n",
        "\n"
      ],
      "metadata": {
        "id": "tImj83NWEdJI"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Get all factors of n\n",
        "import math\n",
        "n = 12\n",
        "factors = set()\n",
        "for i in range(1, int(math.sqrt(n)) + 1):\n",
        "    if n % i == 0:\n",
        "        factors.add(i)\n",
        "        factors.add(n // i)\n"
      ],
      "metadata": {
        "id": "t4Yh3v_uErOY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "**O( n! )**\n",
        "\n",
        "\n",
        "---\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "PXkgcgEdEvZ5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Permutations\n",
        "# Travelling Salesman Problem"
      ],
      "metadata": {
        "id": "_qfaeV6jEzcB"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}