Time Complexities of sorting algorithms

Algorithm

Time Complexity

Best case

Average case

Worst case

Bubble Sort

Ω(n)

θ(n2)

O(n2)

Bucket Sort

Ω(n+k)

θ(n+k)

O(n2)

Heap Sort

Ω(n log(n))

θ(n log(n))

O(n log(n))

Insertion Sort

Ω(n)

θ(n2)

O(n2)

Merge Sort

Ω(n log(n))

θ(n log(n))

O(n log(n))

Quick Sort

Ω(n log(n))

θ(n log(n))

O(n2)

Radix Sort

Ω(nk)

θ(nk)

O(nk)

Selection Sort

Ω(n2)

θ(n2)

O(n2)

Share:

Auto increment addressing mode | UGC NET

UGC NET 2018

Consider the following statements:  
(i) Auto increment addressing mode is useful in  creating self-relocating code.

(ii) If auto increment addressing mode is included  in an instruction set architecture, then an  additional ALU is required for effective  address calculation.  

(iii) In auto increment addressing mode, the  amount of increment depends on the size of  the data item accessed. 

Which of the above statements is/are true?  Choose the correct answer from the code given  below:  
Code:  
(a) (ii) and (iii) only 
(b) (iii) only  
(c) (ii) only 
(d) (i) and (ii) only

Solution:

Addressing modes:

Addressing modes are the ways through which operands are specified.  

The address field in a typical instruction formats are relatively small.

This address field is used to reference the operand in the memory.

Auto increment addressing mode:

Autoincrement mode is similar to register deferred mode in that the address of an operand is stored in a register at runtime. The contents of the register are incremented each time the instruction is performed in autoincrement mode.

Option (iii) is correct, because
In this mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store.

Autoincrement Mode = after operand addressing , the contents of the register is incremented.

Option (i) is not correct, because
Self - relocating code takes always some address in memory and hence auto - increment addressing mode is not used for self - relocating code.

Option (ii) is not correct, becuase
Additional ALU is not required for effective address calculation if auto addressing mode is included in an instruction set architecture.

To know moe about addressing modes : click here.
Share:

In OSI functions of Session Layer is | UGC NET

UGC NET 2018: 

Consider ISO-OSI network architecture reference model. Session layer of this model offer Dialog control, token management and ____________ as services.

A) Synchronization
B) Asynchronization
C) Errors
D) Flow control

Solution:

Functions of Session Layer : 
  • Dialog control
  • Token management
  • Synchronization. 
Functions of Transport layer:
  • Flow control
  • Error corrections




For more information : 

Share:

Minimization of DFA

Construct a minimum state automata equivalent to given automata ?

(RGPV 2008)

Solution:
Transition table for above automata.

State

Input = a

Input = b

->q0 Initial state

q1

q3

q1

q2

q4

q2

q1

q1

q3

q2

q4

q4 Final state

q4

q4


Step 01: Remove steps which are unreachable from initial states.
Step 02: Split final states and non final states.

A0 = {q4}
A1 = {q0,q1,q2,q3}

π0 = {q4}, {q0,q1,q2,q3}

A0 cannot be partition further.

In A1,
q0 is 1 equivalent to q2 for input a, but not equivalent to q1 and q3.
q1 is 1 equivalent to q3 for input a and b, but not to q0 and q2.

So, A1 can be partitioned as,
B0 = {q0, q2}
B1 = {q1, q3}

π1 = {q4}, {q0,q2}, {q1,q3}

Now, B0 and B1 can not be partitioned further.

π2 = {q4}, {q0,q2}, {q1,q3}

π2 = π1

In minimized DFA, we have three states,
  1. {q4}, 
  2. {q0,q2}, 
  3. {q1,q3}

State

Input = a

Input = b

->{q0,q2} Initial state

{q1,q3}

{q1,q3}

{q1,q3}

{q0,q2}

{q4}

{q4} Final state

{q4}

{q4}



Share:

NFA to DFA using Indirect method

NFA to DFA using Indirect method

Step 01 : First convert NFA with ∈ moves to NFA without ∈ moves.
Step 01 :Then convert NFA without ∈ to the DFA.

Let's take an example,

We have a NFA with epsilon moves, now convert it to the NFA without epsilon moves.

NFA with epsilon moves


First convert above NFA to without epsilon moves,

Find ∈-closure of (q1), (q2) and (q3).
  1. ∈-closure of (q1) = {q1, q2, q3} 
  2. ∈-closure of (q2) = {q2, q3}
  3. ∈-closure of (q3) = {q3}

State

0

1

2

->q1

{q1,q2,q3}

{q2,q3}

{q3}

q2

φ

{q2,q3}

{q3}

q3

φ

φ

{q3}


From the above transition table, draw the transition diagram,

NFA without  epsilon

From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.
So, now without ∈ input, q1 and q2 is also treated as final states.
As shown in diagram beabove.

Now, NFA without epsilon to DFA

Using Subset construction method.

Again I am going to use information from this transition table.

State

0

1

2

->q1

{q1,q2,q3}

{q2,q3}

{q3}

q2

φ

{q2,q3}

{q3}

q3

φ

φ

{q3}


Subsets are,
  1. {q1}
  2. {q2}
  3. {q3}
  4. {q1,q2,q3}
  5. {q2,q3}
Treat each subset as state in DFA.
If there is no transition use φ symbol.

State

Input = 0

Input = 1

Input = 2

{q1}

{q1,q2,q3}

{q2,q3}

{q3}

{q2}

φ

{q2,q3}

{q3}

{q3}

φ

φ

{q3}

{q1,q2,q3}

{q1,q2,q3}

{q2,q3}

{q3}

{q2,q3}

φ

{q2,q3}

{q3}

φ

φ

φ

φ


In NFA withoud epsilon, q1, q2, q3 was final states. In subset {q1,q2,q3} and {q2,q3} final states exist.
So these subsets will also treated as final states.

DFA from NFA

Now from the transition table of above DFA,

State

Input = 0

Input = 1

Input = 2

{q1}

{q1,q2,q3}

{q2,q3}

{q3}

{q2}

φ

{q2,q3}

{q3}

{q3}

φ

φ

{q3}

{q1,q2,q3}

{q1,q2,q3}

{q2,q3}

{q3}

{q2,q3}

φ

{q2,q3}

{q3}

φ

φ

φ

φ


We find state {q1,q2,q3} is equivalent to state {q1}, so replce state {q1,q2,q3} by state {q1}.
Simillary, replace state {q2,q3} by state {q2}.

So, new DFA transition table become,

State

Input = 0

Input = 1

Input = 2

{q1}

{q1}

{q2}

{q3}

{q2}

φ

{q2}

{q3}

{q3}

φ

φ

{q3}

φ

φ

φ

φ


And DFA transition diagram,


Practice problems:

Share: