Little o notation: Difference between revisions
imported>Hendra I. Nurdin mNo edit summary |
imported>Aleksander Stos (suspended until found in refs) |
||
| Line 3: | Line 3: | ||
More formally, if ''f'' and ''g'' are real valued functions of the real numbers then the notation <math>f(t)=o(g(t))</math> indicates that | More formally, if ''f'' and ''g'' are real valued functions of the real numbers then the notation <math>f(t)=o(g(t))</math> indicates that | ||
:<math> \lim_{t\to\infty} \frac{f(t)}{g(t)} = 0.</math> | <!-- :<math> \lim_{t\to\infty} \frac{f(t)}{g(t)} = 0.</math> | ||
This means that ''f'' becomes infinitely small with respect to ''g'' when ''t'' increases. In mathematical terms, for every real number <math>\epsilon>0</math> there exists a positive real number <math>T(\epsilon)</math> (note the dependence of ''T'' on <math>\epsilon</math>) such that <math>|f(t)|\leq \epsilon |g(t)|</math> for all <math>t>T(\epsilon).</math> | This means that ''f'' becomes infinitely small with respect to ''g'' when ''t'' increases. In mathematical terms, -->for every real number <math>\epsilon>0</math> there exists a positive real number <math>T(\epsilon)</math> (note the dependence of ''T'' on <math>\epsilon</math>) such that <math>|f(t)|\leq \epsilon |g(t)|</math> for all <math>t>T(\epsilon).</math> | ||
Similarly, if <math>a_n</math> and <math>b_n</math> are two numerical sequences then <math>a_n=O(b_n)</math> means that the fraction <math>\frac{|a_n|}{|b_n|}</math> tends to 0 when <math>n</math> tends to infinity. | Similarly, if <math>a_n</math> and <math>b_n</math> are two numerical sequences then <math>a_n=O(b_n)</math> means that for any <math>\varepsilon>0</math> and ''n'' big enough one has <math>|a_n|\leq \epsilon |b_n|.</math> | ||
<!--the fraction <math>\frac{|a_n|}{|b_n|}</math> tends to 0 when <math>n</math> tends to infinity.--> | |||
The little o notation is also often used to indicate that the absolute value of a real valued function goes to zero around some point at a rate faster than at which the absolute value of another function goes to zero at the same point. For example, suppose that ''f'' is a function with <math>f(t_0)=0</math> for some real number <math>t_0</math>. Then the notation <math>f(t)=o(g(t-t_0))</math>, where ''g(t)'' is a function which is [[continuity|continuous]] at ''t=0'' and with ''g(0)=0'', denotes that for every real number <math>\epsilon>0</math> there exists a [[topological space#Some topological notions|neighbourhood]] <math>N(\epsilon)</math> of <math>t_0</math> such that <math>|f(t)|\leq \epsilon |g(t-t_0)|</math> holds on <math>N(\epsilon)</math>. | The little o notation is also often used to indicate that the absolute value of a real valued function goes to zero around some point at a rate faster than at which the absolute value of another function goes to zero at the same point. For example, suppose that ''f'' is a function with <math>f(t_0)=0</math> for some real number <math>t_0</math>. Then the notation <math>f(t)=o(g(t-t_0))</math>, where ''g(t)'' is a function which is [[continuity|continuous]] at ''t=0'' and with ''g(0)=0'', denotes that for every real number <math>\epsilon>0</math> there exists a [[topological space#Some topological notions|neighbourhood]] <math>N(\epsilon)</math> of <math>t_0</math> such that <math>|f(t)|\leq \epsilon |g(t-t_0)|</math> holds on <math>N(\epsilon)</math>. | ||
Revision as of 01:44, 11 October 2007
The little o notation is a mathematical notation which indicates that the decay (respectively, growth) rate of a certain function or sequence is faster (respectively, slower) than that of another function or sequence. It is often used in particular applications in physics, computer science, engineering and other applied sciences.
More formally, if f and g are real valued functions of the real numbers then the notation indicates that for every real number there exists a positive real number (note the dependence of T on ) such that for all
Similarly, if and are two numerical sequences then means that for any and n big enough one has
The little o notation is also often used to indicate that the absolute value of a real valued function goes to zero around some point at a rate faster than at which the absolute value of another function goes to zero at the same point. For example, suppose that f is a function with for some real number . Then the notation , where g(t) is a function which is continuous at t=0 and with g(0)=0, denotes that for every real number there exists a neighbourhood of such that holds on .
