We use Ө-notation to write worst case running time of insertion sort. But I’m not able to relate properties of Ө-notation with insertion sort, why Ө-notation is suitable to insertion sort. How does the insertion sort function f(n), lies between the c1*n^2 and c2*n^2 for all n>=n0.
插入排序的运行时间为Ө（n^2）意味着它有上界O（n^2）和下界Ω（n^2）我搞不清插入排序下限是Ω（n^2）还是Ω（n）。
最佳答案
_符号的使用：
如果任何函数具有相同的上界和下界，则可以用π-符号来描述它的时间复杂度，它的上界和下界都可以用单记号来指定。它只是简单地说明了函数的特性。
例子，
suppose we have a function ,
f(n) = 4logn + loglogn
we can write this function as
f(n) = Ө(logn)
Because its upper bound and lower bound
are O(logn) and Ω(logn) repectively, which are same
so it is legal to write this function as ,
f(n)= Ө(logn)
证明：
**Finding upper bound :**
f(n) = 4logn+loglogn
For all sufficience value of n>=2
4logn <= 4 logn
loglogn <= logn
Thus ,
f(n) = 4logn+loglogn <= 4logn+logn
<= 5logn
= O(logn) // where c1 can be 5 and n0 =2
**Finding lower bound :**
f(n) = 4logn+loglogn
For all sufficience value of n>=2
f(n) = 4logn+loglogn >= logn
Thus, f(n) = Ω(logn) // where c2 can be 1 and n0=2
so ,
f(n) = Ɵ(logn)
类似地，在插入排序的情况下：
If running time of insertion sort is described by simple function f(n).
In particular , if f(n) = 2n^2+n+1 then
Finding upper bound:
for all sufficient large value of n>=1
2n^2<=2n^2 ------------------- (1)
n <=n^2 --------------------(2)
1 <=n^2 --------------------(3)
adding eq 1,2 and 3, we get.
2n^2+n+1<= 2n^2+n^2+n^2
that is
f(n)<= 4n^2
f(n) = O(n^2) where c=4 and n0=1
Finding lower bound:
for all sufficient large value of n>=1
2n^2+n^2+1 >= 2n^2
that is ,
f(n) >= 2n^2
f(n) = Ω(n^2) where c=2 and n0=1
because upper bound and lower bound are same,
f(n) = Ө(n^2)
if f(n)= 2n^2+n+1 then, c1*g(n) and c2*g(n) are presented by diagram:
在最坏的情况下，插入排序的上界和下界是O（n^2）和Ω（n^2），因此在最坏的情况下，将插入排序的运行写为Ө（n^2）是合法的
最好是Ө（n）。