MathWiki - asymptotics

The need for asymptotic notation: a case study

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:02:20+00:00

The need for asymptotic notation: a case study Consider the following problem. In Python, the numerical computation library numpy provides numpy arrays — a memory- and CPU-efficient alternative to ordinary Python lists. Numpy arrays have one problem, however: unlike Python lists, they cannot be resized (akin to arrays in many other languages like Java and C). Your program is provided with a long list of integers coming from a file, one integer per line. You don't know the number of lines befor…

Big Oh

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:04:48+00:00

Big Oh In this lesson we will introduce our first asymptotic notation: the Big Oh, which can be used for expressing an upper bound for an algorithm's running time. In the previous lesson The need for asymptotic notation: a case study we proved theoretically that for sufficiently large $n$, the running time of the second algorithm satisfies $T_2(n) < dn$$d$$T_2(n) < 0.0021n$$n > 150$$T_2(n) < 0.0021n$$n > 150$$n$$T_2(n) < dn$$d$$n$$T_2(n) < dn$$d$\[T_2 \in O(n).\]$\log n$$n \geq 2$$f$$g$$c\geq…

Big Omega

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:09:16+00:00

Big Omega The big Oh notation considered in the previous lesson is the most widely used asymptotic notation in computer science. The reason is that when designing a software system, we want to be sure that the algorithms we choose will be fast enough to solve our problems at the required input sizes, so we need to know some $T(n)$$n$$T \in O(f)$$f$$T \in O(f)$$T$$f$$T$$g$$g(n)$$n$$g$$g$$f$$g$$c\geq 0$$n$$f(n)\geq c\cdot g(n)$$\geq$$\leq$$f\in \Omega(g)$$c$$n_0$$n > n_0$$f(n) \geq cg(n)$$\Omega…

Multiple variables

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:09:51+00:00

Multiple variables The asymptotic notations can be extended to the case where the functions depend on multiple variables. E. g. if we have an algorithm for searching a string of length $m$ in a text of length $n$, we might be interested in how the worst-case running time $T(m,n)$$m$$n$$f$$g$$f$$g$$c$$m_0$$n_0$$f(m, n)\leq c\cdot g(m, n)$$m \geq m_0$$n \geq n_0$$T(m, n) = 4mn$$g(m, n) = mn^2$$h(m, n)=n^3$$T \in O(g)$$T \not\in O(h)$$nk\in O(n)$$k\to \infty$$n\to\infty$$n \to \infty$$k$$nk\in O(…

Polynomial complexity

Anonymous (anonymous@undisclosed.example.com) — 2014-01-20T09:10:40+00:00

Polynomial complexity The main aim of computer science is develop efficient algorithms for different problems. However, the question what is efficient is not so straightforward. Engineers who program low-level operating system routines try to shave off any assembler level instruction, while scientists who conduct large numerical simulations try to devise algorithms with sub-quadratic complexity. The most liberal definition of efficiency is used by theoretical computer scientists, who consider…

The negligible, the noticeable and the overwhelming

Anonymous (anonymous@undisclosed.example.com) — 2015-07-26T14:34:56+00:00

The negligible, the noticeable and the overwhelming In this lesson we will meet three concepts related to the asymptotic notions that are especially often used in cryptography: the concepts of negligible, overwhelming and noticeable functions. This lesson assumes some basic knowledge of the concept of probability, as covered by lesson $A$$p > 0$$q = 1-p$$2^{-90}$$A^*$$k$$A $$k$$A^*$$P_{\text{fail}}^{A^*}(k) = q^k$$p = \frac12$$q^k = 2^{-k}$$2^{-90}$$A$$90$$p$$A^*$$B$$k$$k$$ck$$c$$P_{\text{fail…