Multivariable asymptotics

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

The following fact may be elementary and obvious to some people, but I'd been confused regarding this topic for some time, so I wrote this blog post.

The definition of the big O notation is usually given for one-variable functions in introductory textbooks, so when I talked or read about graph algorithms, I used notations like O(|V| + |E|) without really understanding their meaning.

Adapting the definition for one-variable functions, I get this definition for multi-variable functions, say, $\text{[math]}$ :

$\text{[math]}$ , iff $\text{[math]}$ s.t. $\text{[math]}$ .

The question is what norm we are talking about. Here are some norms we're used to:

||(x, y)||₁ = |x| + |y| (Manhattan)
$\text{[math]}$ (Euclidean)
||(x, y)||_∞ = max \{|x|, |y|\} (Infinity)

Of course, unless otherwise stated, norm means the Euclidean norm. But the other two norms seems simpler: in computer science x and y are in most cases integers, so why do you have to bother with irrational numbers?

As it turns out, the three norms above are equivalent in terms of defining the meaning of O(g). Suppose $\text{[math]}$ in terms of the Manhattan norm, i.e., $\text{[math]}$ s.t. $\text{[math]}$ . The set of points {(x, y): ||(x, y)||₁ ≥ D} is the region outside a square enclosing the origin, and if we replace the norm with the Euclidean norm, it becomes the region outside a circle. So if we take D^′ so that the circle {(x, y): ||(x, y)||₂ = D^′} encloses the square {(x, y): ||(x, y)||₁ = D}, we have $\text{[math]}$ , and this means $\text{[math]}$ in terms of the Euclidean norm, too. The rest of the proof goes similarly.

EDIT: I've just read that all norms of a finite-dimensional vector space induce the same topology in a textbook. I'd like to know if this is relevant to what I've written.

Комментарии (16)

Написать комментарий?

gen	13 лет назад, # \| 0 As D just denotes the maximum value, for which we still allow f(x, y) to be larger than Cg(x, y), I think the purpose of the norm is simply to evaluate the quantity of (x, y) in some way. So in this case any symmetrical (in relation to x and y) norm will do the job. → Ответить

ikk

13 лет назад, # ^ |

← Rev. 7 →

+10

I suspect that in fact any norm will do. An "asymmetrical" norm like ||(x, y)||_? = max{|x|, 2|y|} gives the same definition of O (you can tell this by replacing 'square' with 'rectangle' in the argument above).

EDIT: By the way, an asymmetrical norm seems to mean a generalization of a norm in which ||v|| is not necessarily equal to || - v||.

→ Ответить

gen

Seems so. Similar to your argument, if we have some norm, than we can both inscribe and exscribe to it some symmetrical norm (say, circle). That means that if the definition works for a circle, then it works for this norm, also (if a circle is inscribed). And contrary: if the definition works for this norm, it works also for a circle (if a circle is excribed). So we have established a bijection of both definitions.

halyavin

Note that this doesn't work for some half-norms like min(|x|,|y|) which can be very useful in practice.

ikk	13 лет назад, # ^ \| +5 What are half-norms? → Ответить

Norm that can be zero on non-zero elements.

Martial

← Rev. 2 →

There is one difference between norms and semi-norms: a semi norm is allowed to assign 0 to some vectors that are not 0.

By the way, min(|x|, |y|) is not a semi-norm, because it doesn't satisfy the triangular inequality; take the two vectors (0, 1) and (1, 0) for a counter-example.

I agree, any norm will do, since all norms are equivalent in a finite dimension space. See the properties of a norm.
If it's a norm, || - v|| should be equal to ||v||, according to the first property.

Well, I mentioned asymmetrical norms because in the first version of the post I used the word "asymmetrical norm" without knowing that's a technical term that refers to diffrent things than I described. (The relative pronoun "which" refers to "a generalization".)

I_love_natalia

All asymmetrical norms are also equivalent in a finite dimension space.

Moreover, all continuous functions f: R^n -> R are equivalent if f(a*x) = a*f(x), for any positive a.

ikk	13 лет назад, # ^ \| 0 That's amazing. The proof below almost applies to asymmetrical norms, but it uses the triangule inequality, so how do you prove it for such continuous mappings in general? → Ответить

In the proof, the triangular inequality is needed to prove the continuity of the norm. To adapt to the case of a continuous function f such that f(a * x) = a * f(x), for any positive a, this part of the proof is not needed anymore.

ikk	13 лет назад, # ^ \| ← Rev. 2 → 0 Ah yes, thanks. (I read the proof, forgot it, read anonymous' post, skimmed the proof again, found the triangle inequality and thought "oh this doesn't apply to continuous mappings in general". I should be more careful.) → Ответить

Thanks for the clarification. It looks confusing that "asymmetric norm" is more general than " norm". Oh well.

ikk	13 лет назад, # ^ \| +5 Here's the link to the proof → Ответить

Блог пользователя ikk