BIG-O, Omega and Theta notations in algorithms

Having the expression for the best, average and worst cases, for all the three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds we need some kind of syntax and that is the subject of the following discussion about different notations. Let us assume that the given algorithm is represented in the form of function f(n).

Big-O Notation:

Big-O Notation gives the tight upper bound of the given function. Generally, it is represented as f(n)=O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n).


For example, f(n) = n4 + 100n2 + 10n + 50 is the given algorithm, then n4 is g(n). That means g(n) gives the maximum rate of growth for f(n) at larger values of n.
Let us see the O-notation with little more details. O- notation defined as O(g(n))={f(n): there exists positive constants c and n0}. g(n) is an asymptotic tight upper bound for f(n). Our objective is to give smallest rate of growth g(n) which is greater than or equals to given algorithm rate of growth f(n).
Generally we discard lower values of n. That means the rate of growth at lower values of n is not important. In the below figure, n0 is the point from which we need to consider the rate of growth for a given algorithm. Below n0 the rate of growth could be different.
Big-O Visualization:
O(g(n)) is the set of functions with smaller or same order of growth as g(n). For example, O(n2) includes O(1), O(nlogn) etc…
Note: Analyze the algorithms at large values of n only. What is that mean is, below n0 we do not care for rate of growth.
No Uniqueness:
There are no unique set of values for n0 and c in providing asymptotic bounds. Let us consider, 100n + 5 = O(n). For this function there are multiple n0 and c values possible.
Solution1: 100n + 5 ≤ 100n + n = 101n ≤ 101n, for all n ≥ 5, n0=5 and c=101 is a solution.
Solution2: 100n + 5 ≤ 100n + 5n = 105n ≤ 105n, for all n ≥ 1, n0=1 and c=105 is also a solution.

Omega-Ω Notation:

Similar to O discussion, this notation gives the tighter lower bound of the given algorithm and we represent it as f(n) = Ω(g(n)). That means, at larger values of n, the lower bound of f(n) is g(n). For example, if f(n) = 100n2 + 10n + 50, g(n) is Ω(n2).
The Ω notation can be defined as Ω(g(n))={f(n): there exists positive constants c and n0such that 0≤cg(n)≤f(n) for all n≥n0}. g(n) is an asymptotic tight lower bound for f(n). Our objective is to give largest rate of growth g(n) which is less than or equal to given algorithms rate of growth f(n).

Theta-Θ Notation:

This notation will decides whether upper and lower bounds of a given algorithm are same. The average running time of algorithm is always between lower bound and upper bound. If the upper bound(O) and the lower bound(Θ) give the small result then Θ notation will have the same rate of growth. As an example, let us assume that f(n) = 10n + n is the expression.
Then it’s tight upper bound g(n) is O(n). The rate of growth in best case is g(n)=O(n).
In this case, rate of growths in the best case and worst case are same. As a result, the average case will also be same. For a given algorithm, if the rate of growths for O and Ω are not same then the rate of growth Θ case may not be same. In this case, we need to consider all possible time complexities and take average of those.
Now, consider the definition of Θ notation. It is defined as Θ(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}. g(n)is an asymptotic tight bound for f(n). Θ(g(n)) is the set of functions with the same order of growth as g(n).
Location: Bengaluru, Karnataka, India

Popular posts from this blog

Hibernate auto increment with example

In previous example we learn how to map java object with database table for manually(not using auto increment) assigned all the values.  To create primary key auto increment application by using hibernate mapping(hbm.xml) or using annotations continue reading this article.  W e need to create a database and create an employee table by using the below query. Table: CREATE table EMPLOYEE( eid integer ( 10 ) primary key not null , firstname varchar ( 30 ), lastname varchar ( 30 ), designation varchar ( 30 ), salary double( 10 , 2 )); Here, we will create a bean/POJO (Plain Old Java Object) class of employee. Employee.java: package com . javatbrains . hibernate ; import java.io.Serializable ; /*This is the POJO class. It contains only Getter and Setter methods*/ public class Employee implements Serializable { private static final long serialVersionUID = - 75885815725314443L ; private int eid ; ...
Read more

how to count the page views by using JSP

To count no.of page's are viewed by user in your application is a challenge in real time application. In this page we will see how to count the page views when user has viewed the page.           Here, we will do one example how many times user has visited each page in our application. In this post we will come to know, how to count the total application page views as well as individually each pages count.           Let us assume my web application name is "Page Counter". For creating the web application in eclipse IDE, Click here . This Page Counter contains three pages, assume that are the different pages in an application. But, there is the link between each other files for navigating from one page to another. Also it will show the total pages view count and individual page view count in all the pages. Let us see, below is my first jsp file,         ...
Read more

Multithreading in java with example

Multithreading  is one of the most important concept in core java. In this article we will learn what is multithreading? , what is the use of it? and What is the use of Synchronization and when to use it?  with detailed examples. At a time, two or more threads are accessing the same object is called as Multithreading  in Java .  First, we will create two threads for two objects. It is also possible to run two or more threads on a single class object. In this case, there is a possibility to get unreliable results. If the two threads are perform same task, then they need same object to be executed each time. For your better understanding, take an example of any reservations like, railway, movie ticket booking,etc. Let us think only one berth is available in a train and two passengers are asking for that berth. The first person has sent a request to allocate that ticket/berth to him. At the same time, the second person also sent a request to allocate that ...
Read more

How to retrieve data from table by using JDBC with example

To retrieve data from mysql data table by using jdbc, we need to confirm weather which table data we need to retrieve. To confirm open your mysql and view all database names by using the ' show databases ' commands in mysql. Then select which is your database name from showing list of database names, by using the ' use <database name> ' command in mysql. Then we need to see all your existing tables by executing the ' show tables ' command. This command gives you the list of existing tables in your selected database. You need to use existing table only you can follow with that. But, here we will see with entirely new which is not existing in mysql database. Now, We will create simple mysql table with minimal columns. create table emp(eno integer(10), ename varchar(30), sal float); The above command creates a new table, we will move further to insert records into emp table by executing the insert which we mentioned in the below. ...
Read more

Prime, Fibonacci and Factorial number with example in java

Prime number, Fibonacci series and Factorial number programs are most commonly asked questions in interview. Read this article to know what is and how to write programs for prime number, fibonacci series and factorial number. Prime Number: prime number is natural number greater than 1 that has no positive divisor other than 1 and itself. A natural number greater than 1 is not a prime number, is called Composite number . For example, 7 is a prime number. Because it can divide with 1 and 7 only. Where as 8 is composite number. Since it has the divisor 2 and 4 in addition to the 1 and 8. The below example represents the finding the passing number is prime number or not. If the passing number is prime number it will print true otherwise it will print false. package com . javatbrains . practice ; public class PrimeNumber { public boolean isPrimeNumber ( int number ) { if ( number <= 1 ) return false ; // There's only one ...
Read more

How to insert images into database using JDBC?

How to insert images into database table by using JDBC? To know about these topic follow the below lines,           Before going to write a JDBC program for inserting images into database table, we need to create a specific table for inserting images column datatype. For creating the database table, execute the below command in MySQL command prompt. 1 2 3 4 CREATE TABLE ` images ` ( ` image_id ` int ( 11 ) NOT NULL AUTO_INCREMENT, ` image_flag ` int ( 11 ) NOT NULL , ` image ` longblob NOT NULL , PRIMARY KEY ( ` image_id ` ));           After executing the above query in MySQL command prompt, execute the below query to know weather the above table query is created or not. 1 Show tables;            When you have executed the above query that will show you the list of table which all exists in the current database. Current tab...
Read more

How to sort list of objects in java with examples

We could achieve list of objects sorting in java by using sort() method which is available under Collections class as well as by using Comparable and Comparator  interfaces. Comparable and Comparator are two interfaces in java used to sort list of objects. These interfaces are available under java.util package along with Collections  class and other classes and interfaces. Comparable interface contains the method of       public int compareTo(Object obj) Comparator interface contains the method of       public int compare(Object obj1, Object obj2) The compare() and compareTo() methods will return negative integer(-1), or zero(0) or positive integer(1). When the first obj1 is less than obj2 method will return negative integer. When obj1 is equals to obj2 will return zero and when obj1 is grater than obj2 it will return positive integer. If it's objects are stored in any Collection classes like ArrayList, H...
Read more

String interview questions and answers

String interview questions and answers are placed the current post as of my experience in interviews. This will helps who are trying to attend interview as fresher as well as experience. If any one is facing any other questions which are not present in the current page, please drop me an email to " subbareddynallamachu@gmail.com ".  Q1:  String is a class or data type? A: String is a class in java.lang package. But, in java, all classes are also are considered as data types. So we can take String as data type also. Q2:  What is the difference between == and equals() methods in java? A: == operator compares the references of the String object. It does not compare the content of the object. equals() method compares the contents. While comparing the Strings, equals method should be used as it yields the correct result. Q3:  What is String constant pool? A: String constant pool is a separate block of memory where the String objects are held by JVM....
Read more

Exception in thread "main" java.lang.NoClassDefFoundError: javax/transaction/SystemException

Exception in thread "main" java.lang.NoClassDefFoundError: javax/transaction/SystemException error we got in Hibernate 4.3 to work with my MySQL database. We are using hibernate code generation tool in Eclipse and we are able to connect to the database using the Hibernate configuration file. When we try to run code in my Main class application is connecting to the database, but transaction is failing and we got the following error: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Exception in thread "main" java . lang . NoClassDefFoundError : javax / transaction / SystemException at java . lang . Class . forName0 ( Native Method ) at java . lang . Class . forName ( Unknown Source ) at org . jboss . logging . Logger . getMessageLogger ( Logger . java : 2248 ) at org . jboss . logging . Logger . getMessageLogger ( Logger . java : 2214 ) at org . hibernate . cfg . Configuration .< clinit >( Configuration . java : 184 ) at be . comp . permanenti...
Read more

Store file into table by using JDBC with example

To store large data files or text files into database table, we will use CLOB (Charecter Large Object) datatype of SQL . By using CLOB it is possible to save entire text book or a file or resume into a column of data table. If your using MySQL database instead of CLOB use LONGTEXT to save file into datatable. For saving files into a data table, we need to create one table which will contains a column type as CLOB to store files. Here, is the query to create a data table. 1 2 3 4 create table myfiles( file_id int ( 10 ), file_name varchar ( 30 ), file_type LONGTEXT); Once table creation completes, these table contains the 3 columns one is file_id represents the file id, file_name represents the name of the file and finally file_type will get save entire file into the table column. Now, we will move to write a JDBC program which will saves the file into the newly creating table. Here is the JDBC program, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Read more