CODEWITHSUNDEEP
algorithmsortingmathtime-complexity
siddstuff
siddstuff

Reputation: 1255

Difference between big-O notation and theta notation, why (theta) Ө-notation is suitable to insertion sort to describe its worst case running time?

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.

Running time of insertion sort as Ө(n^2) implies that it has upper bound O(n^2) and lower bound Ω(n^2). I’m confuse in whether insertion sort lower bound is Ω(n^2) or Ω(n).

enter image description here

Upvotes: 1

Views: 1208

Answers (3)

siddstuff
siddstuff

Reputation: 1255

The use of Ө-notation :

If any function have same both upper bound and lower bound, we can use Ө-notation to describe its time complexity.Both its upper bound and lower bound can be specified with single notation. It simply tells more about the characteristic of the function.

Example ,

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)

Proof:

     **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)

enter image description here

Similarly, in the case of insertion sort: 

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:

enter image description here

In worst case, insertion sort upper bound and lower bound are O(n^2) and Ω(n^2), therefore in worst case it is legal to write the running of insertion sort as Ө(n^2))

In best case, it would be Ө(n).

Upvotes: 4

Khaled.K
Khaled.K

Reputation: 5940

Insertion Sort Time "Computational" Complexity: O(n^2), Ω(n)

O(SUM{1..n}) = O(1/2 n(n+1)) = O(1/2 n^2 + 1/2 n)) ~ O(n^2)

Ө(SUM{1..(n/2)}) = Ө(1/8 n(n+2)) = Ө(1/8 n^2 + 1/4 n) ~ Ө(n^2)

Here is a paper that shows that Gapped Insertion Sort is O(n log n), an optimal version of insertion sort: Gapped Insertion Sort

But if you are looking for faster sorting algorithm, there's Counting Sort which has Time: O(3n) at its worst case when k=n (all symbols are unique), Space: O(n)

Upvotes: 1

banarun
banarun

Reputation: 2321

The best case running time of insertion time is Ө(n) and worst case is Ө(n^2) to be precise. So the running time of insertion sort is O(n^2) not Ө(n^2). O(n^2) means that the running time of the algorithm should be less than or equal to n^2, where as Ө(n^2) means it should be exactly equal to n^2.

The worst case running time will never be less than Ө(n^2). We use Ө(n^2) because it is more accurate.

Upvotes: 1

Related Questions