big_O.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<blockquote class=\"twitter-tweet\"><p lang=\"fa\" dir=\"rtl\">یه الگوریتم با پیچیدگی زمانی n داریم که میتونه ورودی A رو در ۰.۱ ثانیه حل کنه<br>اگر الگوریتم با پیچیدگی زمانی n^2 داشته باشیم که ورودی A رو در ۱۰ روز حل کنه<br>اگر بتونیم الگوریتمی با پیچیدگی زمانی nlogn پیدا کنیم برای ورودی A چقد زمان میبره؟<br>(بزرگ‌ترین واحد با مقدار بزرگ‌تر از ۱)</p>&mdash; Soroosh (@s_soroosh) <a href=\"https://twitter.com/s_soroosh/status/1227861029415260160?ref_src=twsrc%5Etfw\">February 13, 2020</a></blockquote> <script async src=\"https://platform.twitter.com/widgets.js\" charset=\"utf-8\"></script> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "$ O(n)  : ( 0.1 sec)$  problem $\\bf{I}$\n",
    "\n",
    "$ O(n^{2})  : ( 10 days)$  problem $\\bf{ II}$\n",
    "\n",
    "\n",
    "### question:\n",
    "what about $ O(nlogn) $ ?? problem $\\bf{ III}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\bf{I}$ and $\\bf{II}$ \n",
    "\n",
    "$T_{I}(n) = 0.1$\n",
    "\n",
    "$T_{II}(n) = 10 days = 10 *24* 3600 \\simeq 10^{6}$\n",
    "#### :\n",
    "$$\\frac{T_{II}(n)}{T_{I}(n) } \\simeq 10^7$$\n",
    "#### :\n",
    "$$\\frac{T_{II}(n)}{T_{I}(n) } = \\frac{O(n^2)}{O(n)} = \\frac{an^2 + T^{'}_{II}(n)}{bn + T^{'}_{I}(n) }$$\n",
    "#### :\n",
    "از مقدار $ T^{'}_{II}(n)$  و $ T^{'}_{I}(n)$ صرف نظر می‌کنیم\n",
    "#### :\n",
    "$$\\frac{T_{II}(n)}{T_{I}(n) } \\simeq \\frac{an^2 }{bn} = \\frac{a}{b} n $$\n",
    "#### :\n",
    "$$ \\Rightarrow  n = \\frac{b}{a} * 10^7 $$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### مقایسه با nlogn\n",
    "\n",
    "$\\bf{ I}$ and $\\bf{ III}$ \n",
    "\n",
    "\n",
    "$$\\frac{T_{III}(n)}{T_{I}(n) } = ?$$\n",
    "\n",
    "$$\\frac{T_{III}(n)}{T_{I}(n) } = \\frac{O(nlogn)}{O(n)} = \\frac{cnlog(n) + T^{'}_{III}(n)}{bn + T^{'}_{I}(n) } \\simeq \\frac{c}{a} logn  $$\n",
    "\n",
    "\n",
    "$$ = \\frac{c}{a} log (\\frac{b}{a} * 10^7 )  $$\n",
    "\n",
    "$$ = \\frac{c}{a} [log (\\frac{b}{a}) + log(10^7)   ]$$\n",
    "\n",
    "#### define $ k_1 =  \\frac{c}{a}log (\\frac{b}{a}) $ and $k_2 = \\frac{c}{a}$\n",
    "\n",
    "$$ = k_1.k_2 + k_3log(10^7)$$\n",
    "#### :\n",
    "$$ = k_1 + k_2log((10^3)^{\\frac{7}{3}})$$\n",
    "#### :\n",
    "$$\\simeq k_1 + k_2log((2^{10})^{\\frac{7}{3}})$$\n",
    "#### :\n",
    "$$\\simeq k_1 + k_2log((2)^{10 * \\frac{7}{3}})$$\n",
    "#### :\n",
    "$$\\simeq k_1 + k_2 * 10 * \\frac{7}{3}$$\n",
    "#### :\n",
    "$$\\simeq \\frac{c}{a}log (\\frac{b}{a}) + \\frac{c}{a} * 10 * \\frac{7}{3}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}