Take a look at image #1
Let $\mathbb{G}(\mathbb{R}^n, \mathbb{R}^m)$ the vector space of computational
functions, this means, that all functions in $\mathbb{G}$ are computable by an
imaginary but finite computer.
Then there is a mapping $t:\mathbb{G} \times \mathbb{R}^n \rightarrow \mathbb{N}$
that maps a function and an input value to the processor time requiered
to calculate the result.
Let $g: \mathbb{R}^n \rightarrow \mathbb{R}^m$ be a computable function,
and $f: \mathbb{R} \rightarrow \mathbb{N}; x \mapsto \sup\limits_{\|y\| < x} t[g, y]$.
Then the asymptotial runtime exists, if there is a function $r: \mathbb{R} \rightarrow \mathbb{R}$
continuous with
$$ \lim\limits_{x \rightarrow\infty} \frac{f(x)}{r(x)} = c \in \mathbb{R}$$
Then $\mathcal{O}(f) = \mathcal{O}(r)$.
See the rendered output in link #1.
http://quicklatex.com/cache3/a5/ql_ca3ebd33cf7839def6a51c5c735512a5_l3.png
Well the rendered LaTeX is way better to read than just some `maxxt(x) ~ c(s)`.
And I did not specify the norm I am using, although I would usually be using the uniform norm.
And I thought that my setup would be clear. All my colleagues were able to follow me without problem but they did not know the answer.
The basic idea is to expand the simple f(x)/r(x) -> c for x -> oo to a n dimensional vector space (It would be easy to expand the problem to any tensor space then).
So I tried to bypass the problem by adding a functional t that computes the required time (this is just natural) and a function f that inducts some sort of order. By using those one is able to use the lim.
I cannot use `max` in this context as my set of input vectors is open. Using a closed set might be problematic for functions that are defined on open sets.
Well I think I got your point now.
The notation is the notation we use all the time so I assumed everyone would understand it. The text is a translation from a handwritten German text, so please excuse some mistakes.
I still don't get why I cannot use a real norm. I use simple vectors. Wouldn't it be natural to use some kind of norm? And I do not get why a metric is necessary. (Although the presence of a metric is induced by the norm.)
Thank you for being so kind.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics