Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

Jupyter notebook Big Oh Notation/Big Oh Notation.ipynb

120 views
Tweet
Share
Share
Kernel: Python 2

Big Oh Notation

LaTeX in IPython Notebook

Markdown cells in IPython Notebook can process a subset of the LaTeX typesetting language (by far the most widely used method for typesetting mathematical writing). Here is a very nice quick reference with basic mathematics typesetting commands. Below is a mathematical proof using this LaTeX functionality.

Example

Claim: 3n3+6n2log⁡n−7=O(n3)\quad 3n^3 + 6n^2\log n - 7 = O(n^3)\qquad (as n→∞n\to\infty)

Note: In this class log⁡\log refers to the natural logarithm, that is, the logarithm in base ee (sometimes also called ln⁡\ln).

Proof

First, consider the function f(n)=n−log⁡(n)f(n)=n-\log(n). Note that f(1)=1f(1)=1 and that f′(n)=1−1nf'(n)=1-\frac{1}{n}, so f′(n)≥0f'(n)\ge 0 for n≥1n\ge 1. Thus, f(n)≥f(1)=1f(n)\ge f(1)=1 for n≥1n\ge 1, which implies that log⁡(n)≤n\log(n)\le n for n≥1n\ge 1. So, for n≥1n\ge 1, we have

3n3+6n2log⁡n−7≤3n3+6n3−7=9n3−7≤9n3,3n^3 + 6n^2\log n - 7 \le 3n^3 + 6n^3 - 7 = 9n^3 - 7 \le 9n^3,

which proves the claim.

Exercise

Prove that n2=O(2n)n^2=O(2^n) as n→∞n\to\infty. Hint: First argue that if nn is large enough

2log⁡(n)≤nlog⁡(2).2\log(n) \le n\log(2).

Then apply the exponential function exe^x to both sides. You should be careful to check that the inequality remains valid when applying exe^x.

Since,let f(n)=2log(n)-nlog(2) for n≥4,f(n)≤0. Which means 2log(n)≤nlog(2) for n≥4.
Thus, for n≥4, e^(2log(n))≤e^(nlog(2)),thus e^log(n^2)≤e^log(2^n), n^2≤2^n.
Here we proofed n^2=O(2^n)