Asymptotic Notations


Asymptotic notations are used to analyze algorithm’s run time performance. It represent the time complexity of the algorithm for asymptotic analysis. Best case, worst case and average case are very well examine with the asymptotic notations. Asymptotic notations are consider to be input bound scenario as no input is given to the algorithm then it is concluded to work in constant time. It compute the running time of any operation in mathematical unit of computation. For example, consider running time of one operation is f(n) and another operation is g(n2) means that the running time of first operation will increase linearly with the increase in n and the running time of second operation will increase exponentially when n increases. If n is small then the running time of both operation is same. Usually the time taken by algorithm falls under three types : 

  • Best case: Minimum time required for program execution.
  • Average case: Average time required for program execution.
  • Worst case: Maximum time required for program execution.

Following are the commonly used asymptotic notations :
  • O notation
  • Ω Notation
  • θ Notation

Big Oh (O) Notation 
The notation O(n) measures longest amount of time required for an algorithm to complete the execution or the worst case time complexity of an algorithm. It provides the upper bound of an algorithm’s running time.
For example for function f(n)
Ο (f(n)) = { g(n) : there exist a positive constant c and n0 as 0 ≤ f(n) ≤ c*g(n) for all n > n0}

Omega(Ω) Notation
Omega notation measures the best case time complexity of an algorithm or the best time taken to complete the execution. As the Big O notation gives an asymptotic upper bound on function, Omega (Ω) gives an asymptotic lower bound. Omega notation is rarely used notation among all three.


For example for function of f(n)
Ω (f (n)) ≥ { g(n) : there exist a positive constant c and n0 as g(n) ≤ c*f(n) for all n > n0 } 

Theta (Θ) Notation 
The asymptotic notation Θ(n) is used to express both lower bound as well as upper bound of the
algorithm’s running time.

 

For example for function of f(n)
Θ (f(n)) { g(n) if and only if g(n) = Ο (f(n)) and g(n) = Ω (f(n)) for all n > n0 }








Popular posts from this blog

Brief shortnote on Requirement elicitation and requirement analysis

Image
- Requirement elicitation means gathering of requirements. - Perhaps it is most difficult, critical, most error prone and most communication intensive aspect of software development. - The most important goal of software requirement engineering is to find out what the customer really wants. - The users need can be identify only by understanding expectation of the user from the developers. - Requirements are gathered by asking the question to user and writing down their answers and their exceptions of the software that how he want to use software. - Gathering the requirements of users is the most difficult part of the software development, because both developer and user have different mindset regarding the software. - Here, communication of both the parties are the most essential for software product. - There are number of requirement elicitation method. https://en.wikipedia.org/wiki/Requirements_elicitation   - Some people think that one methodology is a...
Read more

Connection oriented protocol / TCP

Image
- Transmission control protocol (TCP) is set of rules used along with the internet protocol (IP) to send the data in the form of message units between the computers. - During the sending of data, IP take care of delivery of the actual whereas the TCP take care of individual units of the data (called as packets). - TCP is known as connection oriented protocol, means that the connection is established and maintain such time as the message is to be exchanged by the application program. - TCP guarantees the delivery of data and also guarantees that the packets will be delivered in the same order in which they were send. - TCP uses a fixed connection, if one application wants to communicate with another via TCP, then it sends the communication request to an exact address after hand-shaking. - Connection establishment via TCP is called as three way handshaking. - The process starts with the server. Server program tells its TCP that it is actually ready to send the request. This...
Read more

Connection-less protocol/ UDP

Image
- The user datagram protocol (UDP) is called as connection-less, unreliable transport protocol. - It provides process to process communication instead of host to host communication. - UDP is very simple protocol using minimum of overhead. - If a process wants to send a message without the care of reliability then it uses UDP. - UDP takes much less interaction between sender and receiver than using TCP and SCTP. - UDP packets called as user data gram having the fixed size header of 8 bytes. Following figure shows the UDP header.
Read more