declared in a method, constructor, or block. Local variables are not visible outside the method.
Instance variables,member or field variables
declared in a class, but outside a method.They are also called member or field variables.
an instance variable is created when an object is created and destroyed when the object is destroyed
Visible in all methods and constructors of the defining class
Class/static variables
declared with the static keyword in a class, but outside a method
There is only one copy per class, regardless of how many objects are created from it
http://leepoint.net/notes-java/data/variables/45local-inst-class.html
Java Static Variables and Methods
http://www.youtube.com/watch?v=gTk_F61_-9k&feature=related
10. Accessing non-static member variables from static methods (such as main)
Many programmers, particularly when first introduced to Java, have problems with accessing member variables from their main method. The method signature for main is marked static - meaning that we don't need to create an instance of the class to invoke the main method. For example, a Java Virtual Machine (JVM) could call the class MyApplication like this :-
MyApplication.main ( command_line_args );
This means, however, that there isn't an instance of MyApplication - it doesn't have any member variables to access! Take for example the following application, which will generate a compiler error message.
public class StaticDemo
{
public String my_member_variable = "somedata";
public static void main (String args[])
{ // Access a non-static member from static method
System.out.println ("This generates a compiler error" + my_member_variable );
}
}
If you want to access its member variables from a non-static method (like main), you must create an instance of the object. Here's a simple example of how to correctly write code to access non-static member variables, by first creating an instance of the object.
public class NonStaticDemo
{
public String my_member_variable = "somedata";
public static void main (String args[])
{
NonStaticDemo demo = new NonStaticDemo();
// Access member variable of demo
System.out.println ("This WON'T generate an error" +
demo.my_member_variable );
}
}
FAQ002: non-static method cannot be accessed from a static context
http://www.youtube.com/watch?v=bWxn_h4T5xI
when you try to access non-static variable through a static method you have to have object reference means that you have to create that object firts to access non-static variable.
Why is access to non-static variables not allowed from static methods in Java
You can not access non-static data from static context in Java simply because non-static variables are associated with a particular instance of object while Static is not associated with any instance
Checked exceptions represent invalid conditions in areas outside the immediate control of the program (invalid user input, database problems, network outages, absent files) are subclasses of Exception
Unchecked exceptions represent defects in the program (bugs) Unchecked runtime exceptions represent conditions that, generally speaking, reflect errors in your program's logic and cannot be reasonably recovered from at run time are subclasses of RuntimeException, and are usually implemented using IllegalArgumentException, NullPointerException, or IllegalStateException
checked exceptions are the exceptions which occur during the compile time of the program whereas Unchecked exceptions are the exceptions which occur during the run time of the program.
Checked exceptions must be explicitly caught or propagated as described in Basic try-catch-finally Exception Handling. Unchecked exceptions do not have this requirement. They don't have to be caught or declared thrown.
Checked Exceptions:
You should compulsorily handle the checked exceptions in your code, otherwise your code will not be compiled. i.e you should put the code which may cause checked exception in try block. "checked" means they will be checked at compiletime itself.
The most perfect example of Checked Exceptions is IOException which should be handled in your code Compulsorily or else your Code will throw a Compilation Error.
Unchecked Exceptions :
Unchecked runtime exceptions represent conditions that, generally speaking, reflect errors in your program's logic and cannot be reasonably recovered from at run time.
With an unchecked exception, however, compiler doesn't force client programmers either to catch the exception or declare it in a throws clause.
The most Common examples are ArrayIndexOutOfBoundException, NUllPointerException ,ClassCastException
An annotation indicates that the declared element should be processed in some special way by a compiler, development tool, deployment tool, or during runtime.
Information for the compiler — Annotations can be used by the compiler to detect errors or suppress warnings.
Compiler-time and deployment-time processing — Software tools can process annotation information to generate code, XML files, and so forth.
Runtime processing — Some annotations are available to be examined at runtime.
Choosing interfaces and abstract classes is not an either/or proposition. If you need to change your design, make it an interface. However, you may have abstract classes that provide some default behavior. Abstract classes are excellent candidates inside of application frameworks
When to use Abstract Class-If we have a base class where all the classes will perform the same function, then we can define that in our Abstract class. If you plan on updating this base class throughout the life of your program, it is best to allow that base class to be an abstract class. Because you can make a change to it and all of the inheriting classes will now have this new functionality
When To use interface – Interfaces are useful when you do not want classes to inherit from unrelated classes just to get the required functionality.It is used where there of chances adding new method in future. Interfaces are more used to set standards
When should I use abstract classes and when should I use interfaces?
Use Interfaces when…
You see that something in your design will change frequently.
If various implementations only share method signatures then it is better to use Interfaces.
you need some classes to use some methods which you don't want to be included in the class, then you go for the interface, which makes it easy to just implement and make use of the methods defined in the interface.
Use Abstract Class when…
If various implementations are of the same kind and use common behavior or status then abstract class is better to use.
When you want to provide a generalized form of abstraction and leave the implementation task with the inheriting subclass.
Abstract classes are an excellent way to create planned inheritance hierarchies. They're also a good choice for nonleaf classes in class hierarchies.
What are the differences between Interface and Abstract class?
In case of abstract class, a class may extend only one abstract class.A Class may implement several interfaces.
An abstract class can have non-abstract methods.All methods of an Interface are abstract.
An abstract class can have instance variables.An Interface cannot have instance variables.
An abstract class can have any visibility: public, private, protected.An Interface visibility must be public (or) none.
An abstract class can contain constructors .An Interface cannot contain constructors
When you declare a method as abstract, can other nonabstract methods access it?
Yes, other nonabstract methods can access a method that you declare as abstract.
If you need to change your design, make it an interface
Abstract classes are excellent candidates inside of application frameworks.
Abstract classes let you define some behaviors; they force your subclasses to provide others. For example, if you have an application framework, an abstract class may provide default services such as event and message handling. Those services allow your application to plug in to your application framework. However, there is some application-specific functionality that only your application can perform. Such functionality might include startup and shutdown tasks, which are often application-dependent. So instead of trying to define that behavior itself, the abstract base class can declare abstract shutdown and startup methods. The base class knows that it needs those methods, but an abstract class lets your class admit that it doesn't know how to perform those actions; it only knows that it must initiate the actions. When it is time to start up, the abstract class can call the startup method. When the base class calls this method, Java calls the method defined by the child class.
Many developers forget that a class that defines an abstract method can call that method as well. Abstract classes are an excellent way to create planned inheritance hierarchies. They're also a good choice for nonleaf classes in class hierarchies
What is an abstract class, and when should it be used?
http://www.javacoffeebreak.com/faq/faq0084.html
What is the difference between interface and abstract class ?
INTERFACE
1.all methods are abstract.
2. does not use abstract keyword before abstract method.
ABSTRACT
1. ATLEAST ONE METHOD IS ABSTRACT.
2. uses the abstract keyword before abstract method.
http://www.geekinterview.com/question_details/14188
Write down three differences between abstract classes and interfaces in Java.
A class can implement any number of interfaces but can subclass at most one abstract class.
An abstract class can have nonabstract methods; all the methods of an interface are effectively abstract.
An abstract class can declare and use fields; an interface cannot,although it can create static final constants.
An abstract class can have methods whose access is public, protected, private, or none (package). An interface’s methods are implicitly public.
An abstract class can define constructors; an interface cannot.
Abstract Classes versus Interfaces
Unlike interfaces, abstract classes can contain fields that are not static and final, and they can contain implemented methods.
Such abstract classes are similar to interfaces, except that they provide a partial implementation, leaving it to subclasses to complete the implementation. If an abstract class contains only abstract method declarations, it should be declared as an interface instead
By comparison, abstract classes are most commonly subclassed to share pieces of implementation.
A single abstract class is subclassed by similar classes that have a lot in common (the implemented parts of the abstract class), but also have some differences (the abstract methods).
http://docs.oracle.com/javase/tutorial/java/IandI/abstract.html
Java interface versus abstract class
An interface differs from an abstract class because an interface is not a class.
An interface is essentially a type that can be satisfied by any class that implements the interface.
Abstract classes are meant to be inherited from, and when one class inherits from another it means that there is a strong relationship between the 2 classes.
With an interface on the other hand, the relationship between the interface itself and the class implementing the interface is not necessarily strong
Java does not allow multiple inheritance
a class can implement multiple interfaces
which could be considered as an alternative to for multiple inheritance.
So, one major difference is that a Java class can inherit from only one abstract class, but can implement multiple interfaces
When to use abstract class and interface in Java
An abstract class is good if you think you will plan on using inheritance since it provides a common base class implementation to derived classes.
An abstract class is also good if you want to be able to declare non-public members. In an interface, all methods must be public.
If you think you will need to add methods in the future, then an abstract class is a better choice. Because if you add new method headings to an interface, then all of the classes that already implement that interface will have to be changed to implement the new methods. That can be quite a hassle.
Interfaces are a good choice when you think that the API will not change for a while.
Interfaces are also good when you want to have something similar to multiple inheritance, since you can implement multiple interfaces.
http://www.programmerinterview.com/index.php/java-questions/interface-vs-abstract-class/
A pattern is a proven (and recurring) solution to a problem in a context. Each pattern describes a problem which occurs over and over again in our environment, and describes its solution to this problem in such a way that we can use this solution a lots of times
What is Refactoring?
Refactoring is a change made to the internal structure of the software to make it easier to understand and cheaper to modify, without changing its observable behaviour.
How do we divide patterns in tiers?
The Sun Java Center has classified the patterns in three tiers. These are:
Presentation tier patterns for web-component tier,
Business tier patterns for business logic (EJB) tier, and
Integration tier patterns for connection to the databases.
The presentation tier patterns are:
Intercepting filter, Front Controller, View Helper, Composite View, Service-to-Worker, and Dispatcher View.
The business tier patterns are:
Business delegate, Value Object, Session Façade, Composite Entity, Value Object Assembler, Value List Handler, and Service Locator.
A design pattern is a solution to a general software problem within a particular context.
Context : A recurring set of situations where the pattern applies.
Problem : A system of forces (goals and constraints) that occur repeatedly in this context.
Solution : A description of communicating objects and classes (collaboration) that can be applied to resolve those forces.
Give an example where you prefer abstract class over interface ?
1. In Java you can only extend one class but implement multiple interface. So if you extend a class you lost your chance of extending another class.
2. Interface are used to represent adjective or behavior e.g. Runnable, Clonable, Serializable etc, so if you use an abstract class to represent behavior your class can not be Runnable and Clonable at same time because you can not extend two class in Java but if you use interface your class can have multiple behavior at same time.
3. On time critical application prefer abstract class is slightly faster than interface
You are writing classes to provide Market Data and you know that you can switch to different vendors overtime like Reuters, wombat and may be even to direct exchange feed , how do you design your Market Data system.
a MarketData interface which will have methods required by client e.g. getBid(), getPrice(), getLevel() etc and MarketData should be composed with a MarketDataProvider by using dependency injection. So when you change your MarketData provider Client won't get affected because they access method form MarketData interface or class
What is main benefit of using factory pattern ? Where do you use it?
Factory pattern’s main benefit is increased level of encapsulation while creating objects. If you use Factory to create object you can later replace original implementation of Products or classes with more advanced and high performance implementation without any change on client layer.
Can you name few design patterns used in standard JDK library?
Decorator design pattern which is used in various Java IO classes,
Singleton pattern which is used in Runtime , Calendar and various other classes,
Factory pattern which is used along with various Immutable classes likes Boolean e.g. Boolean.valueOf and
Observer pattern which is used in Swing and many event listener frameworks.
What is the difference between the bridge pattern and the strategy pattern?
The UML class diagram for the Strategy pattern is the same as the diagram for the Bridge pattern. However, these two design patterns aren't the same in their intent. While the Strategy pattern is meant for behavior, the Bridge pattern is meant for structure.
The Bridge pattern is a structural pattern (HOW DO YOU BUILD A SOFTWARE COMPONENT?).
The Strategy pattern is a dynamic pattern (HOW DO YOU WANT TO RUN A BEHAVIOUR IN SOFTWARE?).
Strategy: you have more ways for doing an operation; with strategy you can choice the algorithm at run-time and you can modify a single Strategy without a lot of side-effects at compile-time;
Bridge decouples the abstraction from implementation so that the two can vary independently.
What is the basic difference between Factory and Abstract Factory Patterns?
With the Factory pattern, you produce implementations (Apple, Banana, Cherry, etc.) of a particular interface -- say, IFruit.
With the Abstract Factory pattern, you produce implementations of a particular Factory interface -- e.g., IFruitFactory. Each of those knows how to create different kinds of fruit.
When to Use the Abstract Factory Pattern Use the Abstract Factory pattern when clients must be decoupled from product classes. Especially useful for program configuration and modification The Abstract Factory pattern can also enforce constraints about which classes must be used with others. It may be a lot of work to make new concrete factories.
Abstract Factory Example1: This specification for the disks to prepare different types of pasta in a pasta maker is the Abstract Factory, and each specific disk is a Factory. all Factories (pasta maker disks) inherit their properties from the abstract Factory. Each individual disk contains the information of how to create the pasta, and the pasta maker does not.
Abstract Factory Example2: The Stamping Equipment corresponds to the Abstract Factory, as it is an interface for operations that create abstract product objects. The dies correspond to the Concrete Factory, as they create a concrete product. Each part category (Hood, Door, etc.) corresponds to the abstract product. Specific parts (i.e., driver side door for 99 camry) corresponds to the concrete products
The Abstract Factory Pattern
Provide an interface for creating families of related or dependent objects without specifying their concrete classes.
The Abstract Factory pattern is very similar to the Factory Method pattern. One difference between the two is that with the Abstract Factory pattern, a class delegates the responsibility of object instantiation to another object via composition whereas the Factory Method pattern uses inheritance and relies on a subclass to handle the desired object instantiation.
Actually, the delegated object frequently uses factory methods to perform the instantiation!
Factory pattern
Factory patterns are examples of creational patterns
Creational patterns abstract the object instantiation process. They hide how objects are created and help make the overall system independent of how its objects are created and composed.
Class creational patterns focus on the use of inheritance to decide the object to be instantiated Factory Method
Object creational patterns focus on the delegation of the instantiation to another object Abstract Factory
Abstract Factory pattern is used to provide a client with set of “family” of objects created by the factory which is determined at runtime. Builder pattern is used to create complex objects with internal parts that must be created in the same order or using a specific algorithm. Factory Method pattern is used to replace class constructors, abstracting the process of object generation in a way that the type of object instantiated can be determined at runtime. Prototype pattern is used to instantiate new object by copying all of the properties of an existing object, creating an independent clone. Singleton pattern ensures single object of a particular class.
all structural patterns in one line? Adapter pattern is used to provide mechanism to link two incompatible types by wrapping the “adaptee” with a class that supports the interface required by the client. Bridge pattern is used to separate the abstract element of a class from the implementation details, providing the means to replace the implementation details without modifying the abstraction. Composite pattern is used to create hierarchical, recursive tree structures of related objects where any element of the structure may be accessed and utilized in a standard manner. Decorator pattern is used to extend or alter the functionality of objects at run-time by wrapping them in an object of a decorator class. Façade pattern is used to define a simplified interface to a more complex subsystem. Flyweight pattern is used to reduce the memory and resource usage for complex models containing many hundreds, thousands or hundreds of thousands of similar objects. Proxy pattern is used to provide a placeholder object, which references an underlying object.
all behavioral patterns in one line? Chain of Responsibility pattern is used to process varied requests, each of which may be dealt with by a different handler. Command pattern is used to express a request, including the call to be made and all of its required parameters, in a command object. Interpreter pattern is used to define the grammar for instructions that form part of a language or notation, whilst allowing the grammar to be easily extended. Iterator pattern is used to provide a standard interface for traversing a collection of items in an aggregate object without the need to understand its underlying structure. Mediator pattern is used to reduce coupling between classes that communicate with each other by sending messages via a mediator object. Memento pattern is used to capture the current state of an object and store it in such a manner that it can be restored at a later time without breaking the rules of encapsulation. Observer pattern is used to allow an object to publish changes to its state. Other objects subscribe to be immediately notified of any changes. State pattern is used to alter the behavior of an object at runtime as its internal state changes. Strategy pattern is used to create an interchangeable family of algorithms from which the required process is chosen at run-time. Template Method pattern is used to define the basic steps of an algorithm and allow the implementation of the individual steps to be changed. Visitor pattern is used to separate a relatively complex set of structured data classes from the functionality that may be performed upon the data that they hold.
Performance: how much time/memory/disk/... is actually used when a program is run. This depends on the machine, compiler, etc. as well as the code.
Complexity: how do the resource requirements of a program or algorithm scale, i.e., what happens as the size of the problem being solved gets larger.
Complexity affects performance but not the other way around
Big-O Notation
We express complexity using big-O notation. For a problem of size N:
constant-time method is "order 1": O(1)
linear-time method is "order N": O(N)
quadratic-time method is "order N squared": O(N2)
How to Determine Complexities
In general, how can you determine the running time of a piece of code? The answer is that it depends on what kinds of statements are used.
1-Sequence of statements
statement 1;
statement 2;
...
statement k;
If each statement is "simple" (only involves basic operations) then the time for each statement is constant and the total time is also constant: O(1).
2-if-then-else statements
Here, either sequence 1 will execute, or sequence 2 will execute. Therefore, the worst-case time is the slowest of the two possibilities: max(time(sequence 1), time(sequence 2)). For example, if sequence 1 is O(N) and sequence 2 is O(1) the worst-case time for the whole if-then-else statement would be O(N)
3-for loops
for (i = 0; i < N; i++) {
sequence of statements
}
The loop executes N times, so the sequence of statements also executes N times. Since we assume the statements are O(1), the total time for the for loop is N * O(1), which is O(N) overall.
4-Nested loops First we'll consider loops where the number of iterations of the inner loop is independent of the value of the outer loop's index. For example:
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
sequence of statements
}
}
The outer loop executes N times. Every time the outer loop executes, the inner loop executes M times. As a result, the statements in the inner loop execute a total of N * M times. Thus, the complexity is O(N * M). In a common special case where the stopping condition of the inner loop is j < N instead of j < M (i.e., the inner loop also executes N times), the total complexity for the two loops is O(N2).
Best-case and Average-case Complexity
Some methods may require different amounts of time on different calls, even when the problem size is the same for both calls. For example, consider the add method that adds an item to the end of the list. In the worst case (the array is full), that method requires time proportional to the number of items in the list (because it has to copy all of them into the new, larger array). However, when the array is not full, add will only have to copy one value into the array, so in that case its time is independent of the length of the list; i.e., constant time.
When do Constants Matter?
Recall that when we use big-O notation, we drop constants and low-order terms. This is because when the problem size gets sufficiently large, those terms don't matter. However, this means that two algorithms can have the same big-O time complexity, even though one is always faster than the other. For example, suppose algorithm 1 requires N2 time, and algorithm 2 requires 10 * N2 + N time. For both algorithms, the time is O(N2), but algorithm 1 will always be faster than algorithm 2. In this case, the constants and low-order terms do matter in terms of which algorithm is actually faster.
Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n
Asymptotic Notations
The goal of computational complexity is to classify algorithms according to their performances. We will represent the time function T(n) using the "big-O" notation to express an algorithm runtime complexity.
Constant Time: O(1)
An algorithm is said to run in constant time if it requires the same amount of time regardless of the input size. Examples:
array: accessing any element
fixed-size stack: push and pop methods
fixed-size queue: enqueue and dequeue methods
Linear Time: O(n)
An algorithm is said to run in linear time if its time execution is directly proportional to the input size, i.e. time grows linearly as input size increases. Examples:
An algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size. Example:
binary search
Quadratic Time: O(n2)
An algorithm is said to run in logarithmic time if its time execution is proportional to the square of the input size. Examples:
bubble sort, selection sort, insertion sort
Definition of "big Omega"
We need the notation for the lower bound.
Definition of "big Theta"
To measure the complexity of a particular algorithm, means to find the upper and lower bounds
Analysis of Algorithms
The term analysis of algorithms is used to describe approaches to the study of the performance of algorithms. In this course we will perform the following types of analysis:
the worst-case runtime complexity of the algorithm is the function defined by the maximum number of steps taken on any instance of size a.
the best-case runtime complexity of the algorithm is the function defined by the minimum number of steps taken on any instance of size a.
the average case runtime complexity of the algorithm is the function defined by an average number of steps taken on any instance of size a.
the amortized runtime complexity of the algorithm is the function defined by a sequence of operations applied to the input of size a and averaged over time.
Example. Let us consider an algorithm of sequential searching in an array.of size n.
Its worst-case runtime complexity is O(n)
Its best-case runtime complexity is O(1)
Its average case runtime complexity is O(n/2)=O(n)
When solving a computer science problem there will usually be more than just one solution. These solutions will often be in the form of different algorithms, and you will generally want to compare the algorithms to see which one is more efficient.
This is where Big O analysis helps – it gives us some basis for measuring the efficiency of an algorithm.
it measures the efficiency of an algorithm based on the time it takes for the algorithm to run as a function of the input size.
Basically, Big-O will want to express how many times the 'n' input items are 'touched'.
The word 'touched' can mean different things in different algorithms - in some algorithms it may mean the number of times a constant is multiplied by an input item, the number of times an input is added to a data structure, etc.
Big O describes the upper (worst case) bound, and Big Omega describes the lower (best case) bound.
Insertion Sort has an upper bound of O(n^2) and a lower bound of Omega(n)
http://www.linuxquestions.org/questions/programming-9/big-o-big-omega-and-big-theta-106102/
asymptotic bounds
Big O, Big Omega, and Big Theta
http://www.youtube.com/watch?v=6Ol2JbwoJp0
http://xoax.net/comp_sci/crs/algorithms/lessons/Lesson6/
This measure of efficiency is called asymptotic complexity,
and is used when dis-regarding certain terms of a function to express the efficiency of an algorithm
or when calculating a function is difficult or impossible and only approximations can be found.
The most commonly used notation for specifying asymptotic complexity—that is, for
estimating the rate of function growth—is the big-O notation
Given two positive-valued functions f and g,consider the following definition: f(n) is O(g(n)) if there exist positive numbers candNsuch that f(n) =cg(n) for all n=N.
This definition reads: f is big-O of g if there is a positive number c such that f is
not larger than cg for sufficiently large ns; that is, for all ns larger than some number N.
The relationship between f and g can be expressed by stating either that g(n) is
an upper bound on the value of f(n) or that, in the long run,fgrows at most as fast
as g.
Algorithms: Big O, Growth Functions, and Worst Case Analysis (1/3)
Big O Part 1 – Linear Complexity
describes the impact of increasing the input data on the time taken for a program to run
big o space complexity
describes the impact of increasing the input data on the extra memory needed by the program
big o describes how the time is taken or how memory is used
big o describes complexity
common sense tells us that a program takes longer when there's more data to work on
linear search or sequential search
brute force approach
an item is searched in an unordered list
time is directly proportional to the amount of data
linear search complexity
big o time complexity is linear, O(n)
Big O Part 2 – Constant Complexity
peek operations, peek over top item wo removing it
LIFO data structure
top is popped, the item is not removed, it is overwritten
no matter how much data is in the stack the time taken remains same
increasing the amount of data makes no difference to the time taken by push or pop operations
stack operations complexity
big o complexity is constant
O(1)
Big O Part 3 – Quadratic Complexity
the dominant term
n^3 is dominant to n^2
bubble sort
comparing,swapping
bubble sort complexity
for n data items, a simple implementation performs (n-1)*(n-1) operations
the dominant term is n^2
big o time complexity is quadratic, O(n^2)
enhanced bubble sort
for n data items, enhanced bubble sort algorithm performs (n-1)+(n-2)+(n-3).....+2+1
(n^2-n)/2
the dominant term is n^2, still O(n^2)
the big o complexity of enhanced bubble sort is still O(n^2)
alternative enhanced bubble sort
best vs worst case scenario
best case scenario, data is already sorted, O(n)
worst case scenario, data is in reverse order, O(n^2)
DAA - Analysis of Algorithms
In theoretical analysis of algorithms, it is common to estimate their complexity in the asymptotic sense, i.e., to estimate the complexity function for arbitrarily large input. The term "analysis of algorithms" was coined by Donald Knuth.
Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Most algorithms are designed to work with inputs of arbitrary length. Analysis of algorithms is the determination of the amount of time and space resources required to execute it.
Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps, known as time complexity, or volume of memory, known as space complexity.
The Need for Analysis
In this chapter, we will discuss the need for analysis of algorithms and how to choose a better algorithm for a particular problem as one computational problem can be solved by different algorithms.
By considering an algorithm for a specific problem, we can begin to develop pattern recognition so that similar types of problems can be solved by the help of this algorithm.
Algorithms are often quite different from one another, though the objective of these algorithms are the same. For example, we know that a set of numbers can be sorted using different algorithms. Number of comparisons performed by one algorithm may vary with others for the same input. Hence, time complexity of those algorithms may differ. At the same time, we need to calculate the memory space required by each algorithm.
Analysis of algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation). However, the main concern of analysis of algorithms is the required time or performance. Generally, we perform the following types of analysis −
Worst-case − The maximum number of steps taken on any instance of size a.
Best-case − The minimum number of steps taken on any instance of size a.
Average case − An average number of steps taken on any instance of size a.
Amortized − A sequence of operations applied to the input of size a averaged over time.
In this context, if we compare bubble sort and merge sort. Bubble sort does not require additional memory, but merge sort requires additional space. Though time complexity of bubble sort is higher compared to merge sort, we may need to apply bubble sort if the program needs to run in an environment, where memory is very limited.
Complexity of an algorithm is analyzed in two perspectives: Time and Space.
Time Complexity
It’s a function describing the amount of time required to run an algorithm in terms of the size of the input. "Time" can mean the number of memory accesses performed, the number of comparisons between integers, the number of times some inner loop is executed, or some other natural unit related to the amount of real time the algorithm will take.
Space Complexity
It’s a function describing the amount of memory an algorithm takes in terms of the size of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself. Again, we use natural (but fixed-length) units to measure this.
Space complexity is sometimes ignored because the space used is minimal and/or obvious, however sometimes it becomes as important an issue as time.
Asymptotic Notations
Execution time of an algorithm depends on the instruction set, processor speed, disk I/O speed, etc. Hence, we estimate the efficiency of an algorithm asymptotically.
Different types of asymptotic notations are used to represent the complexity of an algorithm. Following asymptotic notations are used to calculate the running time complexity of an algorithm.
