Menu
I have the formula a(n) = n * a(n-1) +1 ; a(0) = 0
How can i get the Omega, Theta or O Notation from this without the Master Theorem or did anyone have a good site to understand the explanation
983
(definition) Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of items. Informally, saying some equation f(n) = Ω (g(n)) means it is more than some constant multiple of g(n).
If you have an algorithm running in time Θ(n2), then its running time is also Ω(n). This just means that the running time is linear or worse. In particular, a quadratic running time always has a linear time lower bound, just as 2≥1 holds although 2≠1.
Add up all the operations and simplify it, let's say it is f(n). Remove all the constants and choose the term having the least order or any other function which is always less than f(n) when n tends to infinity, let say it is g(n) then, Big – Omega (Ω) of f(n) is Ω(g(n)).
The Master theorem doesn't even apply, so not being able to use it isn't much of a restriction.
An approach which works here is to guess upper and lower bounds, and then prove these guesses by induction if the guesses are good.
a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 10
a(4) = 41
A reasonable guess for a lower bound is that a(n) >= n! for n>1. This is true for n=1. Suppose it is true for n=k-1.
a(k) = ka(k-1)+1
>= k (k-1)! + 1
>= k!.
So, if it is true for n=k-1, then it is true for n=k, so a(n) >= n! for all positive integers n, and a(n) = Omega(n!).
A reasonable guess for an upper bound is at a(n) <= 2(n!). This is true for the first few values, but it turns out to be a little awkward to prove using induction. Sometimes with inductive proofs, it is better to prove something stronger. In this case, it's better to prove that a(n) < 2(n!), or that a(n)<=2(n!)-1. This is true for n=1. Suppose it is true for n=k-1 for some k-1>=1. Then
a(k) = k(a(k-1))+1
<= k(2(k-1)!-1)+1
= 2(k!) +1-k
<= 2(k-1)!-1.
So, for any n>=1, a(n) < 2(n!). Since we have a lower bound and an upper bound of the form c*(n!), a(n) = Theta(n!).
155
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
