Algorithms: Test 1| Master Theorem
O(n^logb(a)) - if ab^k O((n^k)log(n)) - if a=b^k O(n^k) - if ab^k T(n)= - aT(n/b)+cn^k a=1 - b=2 Theorem (General definition) - let a ≥ 1 and b 1 be constants, let f(n) be a function and let T(n) be defined on the nonnegative integers by the recurrence: T(n) = a T(n/b) + f(n) Note: T(1) = c Has 3 important asymptotic bound properties. (plus a 4th less used one) When is it used? - When we want to describe asymptotic behaviour of an algorithm. Allows us to solve the time complexity of recursive algorithms easier. n/b - can be a ceiling or a floor When do we know to use it? - When we are given a function in this form: f(n) ϵ Θ(n^d) where d ≥ 0 Property 1: T(n) = Θ(n^d) - iff a b^d Property 2: T(n) = Θ(n^d log n) - iff a = b^d Property 3: T(n) = Θ(n^(log_b_a)) - iff a b^d Property 4: T(n) ϵ Θ(n^(log_b_a) log^(k+1) n) (rare) - iff f(n) ϵ Θ(n^(log_b_a) log^k n) for some k ≥ 0 ab^k - T(n) ∈ Θ(n^k) a=b^k - T(n) ∈ Θ(n^k log n) ab^k - T(n) ∈ Θ(n^(logb a)) a - number of recursive calls b - factor divided by
Información del documento
- Subido en
- 12 de julio de 2023
- Número de páginas
- 2
- Escrito en
- 2022/2023
- Tipo
- Examen
- Contiene
- Preguntas y respuestas
