User reported ERROR prereq/slides/complexity-recap.en.xhtml
A content ERROR was logged by "Ali Amr Salah Mohamed Kodera" at the following url:
https://courses.voll-ki.fau.de/course-notes/ai-1?inDocPath=-to8f9d%7E61401cd
The issue as described by the user:
Some symbols are annotated in German throughout this slide
The text highlighted while reporting this issue:
▷We are mostly interested in worst-case
complexity
in AI-1.
▷Definition
Let
𝑆⊆ℕ→ℕ
be a set of
natural number
functions, then we say that analgorithm
𝛼
that terminates in time
𝑡(𝑛)
for all
inputs
of
size
𝑛
has
running time
𝑇(𝛼):=𝑡.
We say that
𝛼
has
time complexity
in
𝑆
(written
𝑇(𝛼)∊𝑆
or colloquially
𝑇(𝛼)=𝑆), iff
𝑡∊𝑆. We say
𝛼
has
space complexity
in
𝑆, iff
𝛼
uses only memory of size
𝑠(𝑛)
on inputs of size
𝑛
and
𝑠∊𝑆.
▷Time/space complexity
depends on size measures.(no canonical one)
▷Definition
The following sets are often used for
𝑆
in
𝑇(𝛼):
Landau set class name rank Landau set class name rank𝒪(1) constant 1 𝒪(𝑛2) quadratic 4𝒪(ln(𝑛)) logarithmic 2 𝒪(𝑛𝑘) polynomial 5𝒪(𝑛) linear 3 𝒪(𝑘𝑛) exponential 6
where
𝒪(𝑔)={𝑓|∃𝑘>0
𝑓≤𝑎𝑘·𝑔}
and
𝑓≤𝑎𝑔
(𝑓
is
asymptotically bounded
by
𝑔), iff there is an
𝑛0∊ℕ, such that
𝑓(𝑛)≤𝑔(𝑛)
for all
𝑛>𝑛0.
For
𝑘'>2
and
𝑘>1
we have
𝒪(1)⊂𝒪(log𝑛)⊂𝒪(𝑛)⊂𝒪(𝑛2)⊂𝒪(𝑛𝑘')⊂𝒪(𝑘𝑛)
▷For AI-1
I expect that given analgorithm, you can determine its
complexity class.
The selected text was in the following section hierarchy:
INNERMOST SECTION FIRST
-
GitLab: https://gl.mathhub.info/MiKoMH/AI/-/blob/main/source/prereq/slides/complexity-recap.en.tex
FetchURL: https://stexmmt.mathhub.info//:sTeX/fulldocument?archive=MiKoMH/AI&filepath=prereq/slides/complexity-recap.en.xhtml&bindings=0_3_Y5ucu1k -
GitLab: https://gl.mathhub.info/MiKoMH/AI/-/blob/main/source/prereq/sec/why-complexity-analysis.en.tex
FetchURL: https://stexmmt.mathhub.info//:sTeX/fulldocument?archive=MiKoMH/AI&filepath=prereq/sec/why-complexity-analysis.en.xhtml&bindings=0_1_SD1s -
GitLab: https://gl.mathhub.info/MiKoMH/AI/-/blob/main/source/prereq/sec/theoinf.en.tex
FetchURL: https://stexmmt.mathhub.info//:sTeX/fulldocument?archive=MiKoMH/AI&filepath=prereq/sec/theoinf.en.xhtml&bindings=0_1_3pGI -
GitLab: https://gl.mathhub.info/MiKoMH/AI/-/blob/main/source/course/notes/notes1.tex
FetchURL: https://stexmmt.mathhub.info//:sTeX/fulldocument?archive=MiKoMH/AI&filepath=course/notes/notes1.xhtml