Skip to main content

Types of Algorithms analysis

To analyse the given algorithm we need to know on which inputs the algorithm will takes less time and long time. We have already seen that an algorithm can be represented in the form of an expression.  That means we represent the algorithm with multiple expressions: one of the case where it takes less time and other for the case where it takes the more time.
In general the first case is called the ‘Best Case’ and second case is called the ‘Worst Case’ of the algorithm. To analyse an algorithm we need some kind of syntax and that forms the base for asymptotic analysis/notation.


There are three types of analysis:
  1. Worst Case:
    • Defines the input for which the algorithm takes long time.
    • Input is the one for which the algorithm runs the slower.
  2. Best Case:
    • Defines the input for which the algorithm takes lowest time.
    • Input is the one for which the algorithm runs the fastest.
  3. Average Case:
    • Provides a prediction about the running time of the algorithm.
    • Assumes that the input is random.
Lower Bound <= Average Time <= Upper Bound
For a given algorithm, we can represent the best, worst and average cases in the form of expression. As an example, let f(n) be the function, which represents the given algorithm.

                    f(n) = n2 + 500, for worst case
                    f(n) = n + 100n + 500, for best case

Similarly for average case too. The expression defines the inputs with which the algorithm takes the average running time f(n).

Popular posts from this blog

JNDI configuration for Tomcat 9 with Oracle

In this article, I am going to place the required source code to get data from the table by using the JNDI configuration. Below are the environment details that I have configured currently. Windows - 7 Oracle - 10g Tomcat - 9 JDK - 8 Eclipse Oxygen Ojdbc6 jar required First, we need to create the Dynamic Web Project. If you don't know how to do <Click Here>. I have faced a lot of issues before getting the output like 405, No driver class to load, etc. I am using JSP & Servlets in the current explanation. Before started writing the application logic, we need to do the below configuration in the installed tomcat directory. Place OJDBC6.jar in the Tomcat LIB directory. Add this Resource under <GlobalNamingResources> in Server.xml file which is present under the conf directory in Tomcat. < Resource name = "jdbc/myoracle" global= "jdbc/myoracle" auth = "Container" type= "javax.sql.DataSource" driverClass...

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 ...

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 ...