Asymptotic Analysis

Asymptotic Analysis

In this tutorial, you will learn what asymptotic notations are. Also, you will learn about Big-O notation, Theta notation and Omega notation.
The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.
An algorithm may not have the same performance for different types of inputs. With the increase in the input size, the performance will change.
The study of change in performance of the algorithm with the change in the order of the input size is defined as asymptotic analysis.

Asymptotic Notations

Asymptotic notations are the mathematical notations used to describe the running time of an algorithm when the input tends towards a particular value or a limiting value.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is linear i.e. the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic) to sort the elements i.e. the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time.These durations are denoted using asymptotic notations.
There are mainly three asymptotic notations: Theta notation, Omega notation and Big-O notation.

Theta Notation (Θ-notation)

Theta notation encloses the function from above and below. Since, it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average case complexity of an algorithm.
Theta notation
For a function g(n), Θ(g(n)) is given by the relation:
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0
          such that 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set Θ(g(n)) if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n), for sufficiently large n.
If a function f(n) lies anywhere in between c1g(n) and c2g(n) for all n ≥ n0, then f(n) is said to be asymptotically tight bound.

Big-O Notation (O-notation)

Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives the worst case complexity of an algorithm.
Big-O notation
O(g(n)) = { f(n): there exist positive constants c and n0
          such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set O(g(n)) if there exists a positive constant c such that it lies between 0 and cg(n), for sufficiently large n.
For any value of n, the running time of an algorithm does not cross time provided by O(g(n)).
Since it gives the worst case running time of n algorithm, it is widely used to anlayze an algorithm as we are always interested in worst case scenario.

Omega Notation (Ω-notation)

Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides best case complexity of an algorithm.
Omega Notation
Ω(g(n)) = { f(n): there exist positive constants c and n0 
          such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
The above expression can be described as a function f(n) belongs to the set Ω(g(n)) if there exists a positive constant c such that it lies above cg(n), for sufficiently large n.
For any value of n, the minimum time required by the algorithm is given by Omega Ω(g(n)).

Comments

Post a Comment

Popular posts from this blog

C Programming Tutorials

This is a complete step by step procedure of learning programming language. Do you want to learn C or C++ instead? Check out our Practical Blog and Tutorial. Here You will get the information of Data Type, Variable, Operator(Arithmetic, Comparison and Conditional), Function(User-defined and Built-in), Conditional Statement(IF, IF ELSE, GOTO and SWITCH), Looping(FOR,  WHILE and DO-WHILE), Pointer and Pointer Array, Structure, Array(1D, 2D and MULTI DIMENSIONAL) and File Programming etc. Further More you will get lots of program of Logics, Graphics, Game and Mathematics etc. Link : C Programming Blog
Read more

DataStructure and Algorithm

Data structures and Algorithm in C or C++ documentations are available here. You will get complete Algorithm, Theorem, Prove and pseodocode and also executable source code here. Learn about Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, Radix Sort, Shell Sort, Quick Sort, Link List Programming, Linear Array Programming, Binary Search and Linear Search etc. Simplified presentation of Arrays, Recursion, Linked Lists, Queues, Trees, Graphs, Sorting, Searching Methods and Hashing. Reference: Schaum's Outlines - Data Structures with C Introduction What is an algorithm? Why you should learn algorithms Algorithm Analysis Big-O notation Sorting Insertion Sort Selection Sort Bubble Sort Heap Sort Merge Sort Quick Sort Shell Sort Counting Sort Radix Sort Bucket Sort Basic Data Structures Stack Queue Circular Queue Linked List Types of Linked List Linked List Operations Advanced Data Structu...
Read more

PL SQL in Oracle

An Oracle database is a collection of data treated as a unit. The purpose of a database is to store and retrieve related information. A database server is the key to solving the problems of information management. This Oracle PL SQL tutorial blog teaches you the basics of programming in PL/SQL with appropriate examples. You can use this tutorial as your guide or reference while programming with PL SQL. I will be making this Oracle PL SQL programming tutorial as often as possible to share my knowledge in PL SQL and help you in learning PL SQL better. Our Blog covers the practice examples of Introduction to PL/SQL, Advantages of PL/SQL, Variables, Constants, Records, Conditional Statements, Iterative Statements, PL/SQL Cursors, Explicit Cursors, PL/SQL Procedures, PL/SQL Functions, Parameters-Procedure, Function, Exception Handling and Triggers etc. Link: PLSQL Programming using Orac...
Read more