JVM, JRE and JDK

What are JVM, JRE and JDK

http://www.javatpoint.com/internal-details-of-jvm

http://www.javabeat.net/what-is-the-difference-between-jrejvm-and-jdk/

http://blog.jamesdbloom.com/JVMInternals.html

http://javatipseveryday.com - Discover the Secrets to Become a Java Expert in 365 days!

Hi friends, Today I’m going to talk with you about the JVM, JRE and JDK. As a Java programmer, you should understand these basic stuffs clearly. It’s like you should see the characteristics and personality of your girlfriend or partner.

1. What is JVM?

JVM stands for Java Virtual Machine. It is an abstract computing machine that is responsible for executing Java programs. When you write a Java program, the source code is compiled into byte code which is understandable by the JVM. Upon execution, the JVM translates byte code into machine code of the target operating system. The JVM is the cornerstone of the Java programming language. It is responsible for the very well-known feature of Java: cross-platform. That means you can write a Java program once and run it anywhere: Windows, Linux, Mac and Solaris, as long as JRE is installed on the host operating system. Every time you run a Java program, the JVM is started to execute and manage the program’s execution. The JVM is running in two modes: client (default) and server. An Oracle’s implementation for JVM is called Java HotSpot VM.

2. What is JRE?

JRE stands for Java Runtime Environment. It provides the libraries, JVM and other components necessary for you to run applets and applications written in the Java programming language.

The JRE contains standard tools such as java, keytool, policytool,… but it doesn’t contain compilers or debuggers for developing applets and applications. When you deploy your Java applications on client’s computer, the client needs a JRE to be installed.

3. What is JDK?

JDK stands for Java Development Kit. It’s a superset of JRE. The JDK includes the JRE plus command-line development tools such as compilers (javac) and debuggers (jdb) and others (jar, javadoc, etc) that are necessary or useful for developing applets and applications. Therefore, as a Java programmer, you have to install JDK as a minimum requirement for the development environment. To summary:

• JVM: is the virtual machine that runs Java applications. The JVM makes Java platform-independence.
• JRE = JVM + standard libraries: provides environment for executing Java applications.
• JDK = JRE + development tools for compiling and debugging Java applications.

The following picture depicts the relationship among JVM, JRE and JDK: Okay, so far I have covered the basic information about the 3 cornerstones in Java programming: JVM, JRE and JDK. I hope you are now able to identify the differences among these components. And here are some tips:

• You should have both JRE and JDK installations (setup) on your computer. You will need both during the development process.
• You should have multiple versions of JDK and JRE installed: 1.5, 1.6, 1.7 and 1.8 for different testing purposes in the future.
• You should install both 32-bit and 64-bit versions.
• When installing the JDK, remember to check ‘Install Demos and Samples’. Then you can explore various interesting examples in the demo directory under JDK’s installation path.
• Only the JDK includes source code of the Java runtime libraries. You can discover the source code in the src.zip file which can be found under JDK’s installation directory.

4. Where to download JRE and JDK?

The starting point is java.oracle.com, but you can go directly to this: http://www.oracle.com/
technetwork/java/javase/downloads/index.html.

Thursday, December 29, 2011

Difference between JRE JVM and JDK in Java Programming language

JRE, JVM and JDK are three terms you often heard in conjunction with Java programming language and most people either confuse between them or think they all are same. In this java article we will what is Java Run-time (JRE), what is Java virtual Machine (JVM) and what is Java development Kit (JDK) along with Just in Time compiler or JIT. Once you know what JRE, JVM or JDK means you can differentiate them easily by yourself.  This article is in continuation of Difference between Comparable and Comparator in Java and Difference between ConcurrentHashMap and Synchronized-map.

JRE JVM and JDK in Java Programming language

Java Runtime Environment (JRE)

Java is every where in browser, in mobile, in TV or in set-top boxes and if you are into Java programming language than you know that Java code which is bundled in JAR (Java archive) file require Java virtual machine JVM to execute it. Now JVM is an executable or program like any other program and you can install that into your machine. You have seen browser often suggesting download JRE to run a Java Applet downloaded from Internet. Various version of JRE are available in java.oracle.com and most of the user who just want to execute Java program inside browser or standalone downloads JRE. All browsers including Internet Explorer, Firefox and Chrome can work with JRE.

Java Virtual Machine (JVM)

When you download JRE and install on your machine you got all the code required to create JVM. Java Virtual Machine is get created when you run a java program using java command e.g. java HelloWorld. JVM is responsible for converting byte code into machine specific code and that's why you have different JVM for Windows, Linux or Solaris but one JAR can run on all this operating system. Java Virtual machine is at heart of Java programming language and provide several feature to Java programmer including Memory Management and Garbage Collection, Security and other system level services. Java Virtual Machine can be customized e.g we can specify starting memory or maximum memory of heap size located inside JVM at the time of JVM creation. If we supplied invalid argument to java command it may refuse to create Java Virtual Machine by saying "failed to create Java virtual machine: invalid argument". In short Java Virtual Machine or JVM is the one who provides Platform independence to Java.

Java Development Kit (JDK)

JDK is also loosely referred as JRE but its lot more than JRE and it provides all the tools and executable require to compile debug and execute Java Program. Just like JRE, JDK is also platform specific and you need to use separate installer for installing JDK on Linux and Windows. Current Version of JDK is 1.7 which is also referred as Java7 and it contains javac (java compiler) based on programming rules of Java7 and Java which can execute java7 code with new features like String in Switch, fork-join framework or Automatic Resource Management. When you install JDK, installation folder is often referred as JAVA_HOME. All binaries are located inside JAVA_HOME/bin which includes javac, java and other binaries and they must be in your system PATH in order to compile and execute Java programs. For details on Path see how to set PATH for Java in Windows and UNIX.

Difference between JRE, JDK and JVM

In short here are few differences between JRE, JDK and JVM:

1)  JRE and JDK come as installer while JVM are bundled with them.

2)  JRE only contain environment to execute java program but doesn’t contain other tool for compiling java program.

3)  JVM comes along with both JDK and JRE and created when you execute Java program by giving “java” command.

Just in Time Compiler (JIT)

Initially Java has been accused of poor performance because it’s both compiles and interpret instruction. Since compilation or Java file to class file is independent of execution of Java program do not confuse. Here compilation word is used for byte code to machine instruction translation. JIT are advanced part of Java Virtual machine which optimize byte code to machine instruction conversion part by compiling similar byte codes at same time and thus reducing overall execution time. JIT is part of Java Virtual Machine and also performs several other optimizations such as in-lining function.

That’s all on JRE, JDK and Java Virtual machine and difference between them. Though they look similar they are different and having a clear idea of JVM, JIT or JDK helps in java programming.

Java Tutorial you may like:

What is abstraction in Java with Example
How to Convert String to Date in Java

What is PolyMorphism in Java

How to Convert Double to String in Java

How Substring in Java works

Top Spring Interview questions for Java Programmer

Read more: http://javarevisited.blogspot.com/2011/12/jre-jvm-jdk-jit-in-java-programming.html#ixzz3hI4sfnQs

Generics

What are Java generics?

Java Generics, sometimes used as a plural noun (generics) and sometimes as a singular noun (Generics), is a language feature of Java that allows for the definition and use of generic types and methods.
'Java Generics' is a technical term denoting a set of language features related to the definition and use of generic types and methods . Generic types or methods differ from regular types and methods in that they have type parameters. Examples of generic types can be found in the Collections framework of the J2SE 5.0 platform libraries. A class like LinkedList<E> is a generic type.  It has a type parameter E that represents the type of the elements stored in the list.  Instead of just using a LinkedList , not saying anything about the type of elements the list contains, we can use a LinkedList<String> or a LinkedList<Integer> , thereby specifying that we mean a list of strings or integral values respectively. Generic types are instantiated to form parameterized types by providing actual type arguments that replace the formal type parameters.  A class likeLinkedList<E> is a generic type, that has a type parameter E . Instantiations, such as LinkedList<String> or a LinkedList<Integer> , are called parameterized types, and String and Integer are the respective actual type arguments.
What is the primary purpose of Java generics?

Java generics were invented primarily for implementation of generic collections.

The need for generic types stems mainly from the implementation and use of collections, like the ones in the Java Collections framework.  Programmers often want to specify that a collection contains elements of a certain type, such as a list of integral values or a list of strings.  The Collections framework in non-generic Java did not offer any homogenous collections of elements of the same type.  Instead, all collections were holding Object references and for that reason they were potentially heterogenous, that is, a mix of objects of different types.  This was also visible in the collection APIs: the non-generic collections accepted objects of arbitrary type for insertion into the collection and returned an Object reference when an element was retrieved from the collection (see packagejava.util in Java 1.4). In non-generic Java, homogenous collections of elements had required implementation of different classes, such as a class IntegerList and a class StringListfor holding integral values and strings respectively. Naturally, implementing a separate collection class for  every conceivable element type is neither feasible nor desirable.  A more reasonable goal is to have a single implementation of the collection class and use it to hold elements of different types.  In other words, rather than implementing a class IntegerList and StringList , we want to have one generic implementation List that can be easily used in either case, as well as in other unforeseen cases. This is what generics are for: the implementation of one generic class can be instantiated for a variety of types.  There is one generic class List in the generic collections framework (see package java.util in Java 5.0).  It permits specification of List<Integer> , List<String> , etc. each of which is a homogenous collection of integral values, strings, etc.  In generic Java, the generic class List is a so-called generic class that has a type parameter.  Uses such asList<Integer> and List<String> are so-called parameterized types .  They are instantiations of the generic class, where the type parameter is replaced by the concrete type arguments Integer and String . The use of the Java generics language features were initially motivated by the need to have a mechanism for efficient implementation of homogenous collections, but the language feature is not restricted to collections. The J2SE 5.0 platform libraries contains numerous examples of generic types and methods that have nothing to do with collections.  Examples are the weak and soft references in package java.lang.ref , which are special purpose references to objects of a particular type represented by a type parameter.  Or the interface Callable in package java.util.concurrent , which represents a task and has a callmethod that returns a result of a particular type represented by a type parameter. Even class Class in package java.lang is a generic class since Java 5.0, whose type parameter denotes the type that the Class object represents.

What is the benefit of using Java generics?

Early error detection at compile time.
Using a parameterized type such as LinkedList<String> , instead of LinkedList , enables the compiler to perform more type checks and requires fewer dynamic casts. This way errors are detected earlier, in the sense that they are reported at compile-time by means of a compiler error message rather than at runtime by means of an exception. Consider the example of a LinkedList<String> . The type LinkedList<String> expresses that the list is a homogenous list of elements of type String .  Based on the stronger information the compiler performs type checks in order to ensure that a LinkedList<String> contains only strings as elements. Any attempt to add an alien element is rejected with a compiler error message. Example (using a parameterized type): LinkedList<String> list = new LinkedList<String>(); list.add("abc");       // fine list.add(new Date());  // error Using a plain LinkedList , the compiler had not issued any message and both elements would have been added to the list. This is because the non-parameterizedLinkedList does not mandate that all elements must be of the same or any particular type. A non-parameterized list is a sequence of elements of type Object and hence arbitrary. Same example (using a non-parameterized type): LinkedList list = new LinkedList(); list.add("abc");       // fine list.add(new Date());  // fine as well Since it is ensured that a LinkedList<String> contains strings it is not necessary to cast an element retrieved from the list to type String . Example (using a parameterized type): LinkedList<String> list = new LinkedList<String>(); list.add("abc");  String s = list.get(0);  // no cast needed Using a plain LinkedList , there is no knowledge and no guarantee regarding the type of the element retrieved.  All retrieval methods return  an Object reference, which must be cast down to the actual type of the element retrieved. Same example (using a non-parameterized type): LinkedList list = new LinkedList(); list.add("abc");  String s = (String)list.get(0);  // cast required The cast would fail at runtime with a ClassCastException in case the element retrieved is not of type String .  This type of runtime failure cannot happen with a parameterized list because the compiler already prevents insertion of an alien element into the sequence.

What does type-safety mean?

In Java, a program is considered type-safe if it compiles without errors and warnings and does not raise any unexpected ClassCastException s at runtime.

The idea is that a well-formed program enables the compiler to perform enough type checks based on static type information that no unexpected type error can occur at runtime.  An unexpected type error in this sense is a ClassCastException being raised without any visible cast expression in the source code.

JSP

http://javarevisited.blogspot.in/2011/10/jsp-interview-questions-answers-for.html

http://www.journaldev.com/1162/java-multi-threading-concurrency-interview-questions-with-answers#thread-join
http://javarevisited.blogspot.in/2013/01/difference-between-identityhashmap-and-hashmap-java.html

Questions to Ask in the interview

Top 25 Most Frequently Asked Interview Core Java Interview Questions And Answers

We are sharing 25 java interview questions , these questions are frequently asked by the recruiters.Java questions can be asked from any core java topic . So we try our best to provide you the java interview questions and answers for experienced which should be in your to do list before facing java questions in  technical interview  .

Top 25  Java Interview Questions :

1. Which two method you need to implement for key Object in HashMap ?

In order to use any object as Key in HashMap, it must implements equals and hashcode method in Java. Read How HashMap works in Java  for detailed explanation on how equals and hashcode method is used to put and get object from HashMap. 

2. What is immutable object? Can you write immutable object?Immutable classes are Java classes whose objects can not be modified once created. Any modification in Immutable object result in new object. For example is String is immutable in Java. Mostly Immutable are also final in Java, in order to prevent sub class from overriding methods in Java which can compromise Immutability. You can achieve same functionality by making member as non final but private and not modifying them except in constructor.

3. What is the difference between creating String as new() and literal?

When we create string with new() Operator, it’s created in heap and not added into string pool while String created using literal are created in String pool itself which exists in PermGen area of heap.

String s = new String("Test");
 
does not  put the object in String pool , we need to call String.intern() method which is used to put  them into String pool explicitly. its only when you create String object as String literal e.g. String s = "Test" Java automatically put that into String pool.

4. What is difference between StringBuffer and StringBuilder in Java ?

Classic Java questions which some people thing tricky and some consider very easy. StringBuilder in Java is introduced in Java 5 and only difference between both of them is that Stringbuffer methods are synchronized while StringBuilder is non synchronized. See StringBuilder vs StringBuffer for more differences.

5.  Write code to find the First non repeated character in the String  ?

Another good Java interview question, This question is mainly asked by Amazon and equivalent companies. See first non repeated character in the string : Amazon interview question

6. What is the difference between ArrayList and Vector ?
This question is mostly used as a start up question in Technical interviews  on the topic of Collection framework . Answer is explained in detail here Difference between ArrayList and Vector .

7. How do you handle error condition  while writing stored procedure or accessing stored procedure from java?

This is one of the tough Java interview question and its open for all, my friend didn't know the answer so he didn't mind telling me. my take is that stored procedure should return error code if some operation fails but if stored procedure itself fail than catching SQLException is only choice.

8. What is difference between Executor.submit() and Executer.execute() method ?

There is a difference when looking at exception handling. If your tasks throws an exception and if it was submitted with execute this exception will go to the uncaught exception handler (when you don't have provided one explicitly, the default one will just print the stack trace to System.err). If you submitted the task with submit any thrown exception, checked exception or not, is then part of the task's return status. For a task that was submitted with submit and that terminates with an exception, the Future.get will re-throw this exception, wrapped in an ExecutionException.

9. What is the difference between factory and abstract factory pattern?

Abstract Factory provides one more level of abstraction. Consider different factories each extended from an Abstract Factory and responsible for creation of different hierarchies of objects based on the type of factory. E.g. AbstractFactory extended by AutomobileFactory, UserFactory, RoleFactory etc. Each individual factory would be responsible for creation of objects in that genre.

You can also refer What is Factory method design pattern in Java to know more details.

10. What is Singleton? is it better to make whole method synchronized or only critical section synchronized ?

Singleton in Java is a class with just one instance in whole Java application, for example java.lang.Runtime is a Singleton class. Creating Singleton was tricky prior Java 4 but once Java 5 introduced Enum its very easy. see my article How to create thread-safe Singleton in Java for more details on writing Singleton using enum and double checked locking which is purpose of this Java interview question.

11. Can you write critical section code for singleton?

This core Java question is followup of previous question and expecting candidate to write Java singleton using double checked locking. Remember to use volatile variable to make Singleton thread-safe.

12. Can you write code for iterating over hashmap in Java 4 and Java 5 ?

Tricky one but he managed to write using while and for loop.

13. When do you override hashcode and equals() ?
Whenever necessary especially if you want to do equality check or want to use your object as key in HashMap.

14. What will be the problem if you don't override hashcode() method ?
You will not be able to recover your object from hash Map if that is used as key in HashMap.
See here  How HashMap works in Java for detailed explanation.

15. Is it better to synchronize critical section of getInstance() method or whole getInstance() method ?
Answer is critical section because if we lock whole method than every time some one call this method will have to wait even though we are not creating any object)

16. What is the difference when String is gets created using literal or new() operator ?
When we create string with new() its created in heap and not added into string pool while String created using literal are created in String pool itself which exists in Perm area of heap.

17. Does not overriding hashcode() method has any performance implication ?
This is a good question and open to all , as per my knowledge a poor hashcode function will result in frequent collision in HashMap which eventually increase time for adding an object into Hash Map.

18. What’s wrong using HashMap in multithreaded environment? When get() method go to infinite loop ?
Another good question. His answer was during concurrent access and re-sizing.

19.  What do you understand by thread-safety ? Why is it required ? And finally, how to achieve thread-safety in Java Applications ? 

Java Memory Model defines the legal interaction of threads with the memory in a real computer system. In a way, it describes what behaviors are legal in multi-threaded code. It determines when a Thread can reliably see writes to variables made by other threads. It defines semantics for volatile, final & synchronized, that makes guarantee of visibility of memory operations across the Threads.

Let's first discuss about Memory Barrier which are the base for our further discussions. There are two type of memory barrier instructions in JMM - read barriers and write barrier.

A read barrier invalidates the local memory (cache, registers, etc) and then reads the contents from the main memory, so that changes made by other threads becomes visible to the current Thread.
A write barrier flushes out the contents of the processor's local memory to the main memory, so that changes made by the current Thread becomes visible to the other threads.
JMM semantics for synchronized
When a thread acquires monitor of an object, by entering into a synchronized block of code, it performs a read barrier (invalidates the local memory and reads from the heap instead). Similarly exiting from a synchronized block as part of releasing the associated monitor, it performs a write barrier (flushes changes to the main memory)
Thus modifications to a shared state using synchronized block by one Thread, is guaranteed to be visible to subsequent synchronized reads by other threads. This guarantee is provided by JMM in presence of synchronized code block.

JMM semantics for Volatile  fields
Read & write to volatile variables have same memory semantics as that of acquiring and releasing a monitor using synchronized code block. So the visibility of volatile field is guaranteed by the JMM. Moreover afterwards Java 1.5, volatile reads and writes are not reorderable with any other memory operations (volatile and non-volatile both). Thus when Thread A writes to a volatile variable V, and afterwards Thread B reads from variable V, any variable values that were visible to A at the time V was written are guaranteed now to be visible to B.

Let's try to understand the same using the following code

Data data = null;

volatile boolean flag = false;

Thread A

-------------

data = new Data();

flag = true; <-- writing to volatile will flush data as well as flag to main memory

Thread B

-------------

if(flag==true){ <-- as="" barrier="" data.="" flag="" font="" for="" from="" perform="" read="" reading="" volatile="" well="" will="">

use data; <!--- data is guaranteed to visible even though it is not declared volatile because of the JMM semantics of volatile flag.

}

20.  What will happen if you call return statement or System.exit on try or catch block ? will finally block execute?

This is a very popular tricky Java question and its tricky because many programmer think that finally block always executed. This question challenge that concept by putting return statement in try or catch block or calling System.exit from try or catch block. Answer of this tricky question in Java is that finally block will execute even if you put return statement in try block or catch block but finally block won't run if you call System.exit form try or catch.

19. Can you override private or static method in Java ?

Another popular Java tricky question, As I said method overriding is a good topic to ask trick questions in Java.  Anyway, you can not override private or static method in Java, if you create similar method with same return type and same method arguments that's called method hiding. 

20. What will happen if we put a key object in a HashMap which is already there ?

This tricky Java questions is part of How HashMap works in Java, which is also a popular topic to create confusing and tricky question in Java. well if you put the same key again than it will replace the old mapping because HashMap doesn't allow duplicate keys. 

21. If a method throws NullPointerException in super class, can we override it with a method which throws RuntimeException?

One more tricky Java questions from overloading and overriding concept. Answer is you can very well throw super class of RuntimeException in overridden method but you can not do same if its checked Exception. 

22. What is the issue with following implementation of compareTo() method in Java

public int compareTo(Object o){

   Employee emp = (Employee) emp;

   return this.id - o.id;

}

23. How do you ensure that N thread can access N resources without deadlock

If you are not well versed in writing multi-threading code then this is real tricky question for you. This Java question can be tricky even for experienced and senior programmer, who are not really exposed to deadlock and race conditions. Key point here is order, if you acquire resources in a particular order and release resources in reverse order you can prevent deadlock. 

24. What is difference between CyclicBarrier and CountDownLatch in Java

Relatively newer Java tricky question, only been introduced form Java 5. Main difference between both of them is that you can reuse CyclicBarrier even if Barrier is broken but you can not reuse CountDownLatch in Java. See CyclicBarrier vs CountDownLatch in Java for more differences.

25. Can you access non static variable in static context?

Another tricky Java question from Java fundamentals. No you can not access static variable in non static context in Java. Read why you can not access non-static variable from static method to learn more about this tricky Java questions.

Spring

http://www.mkyong.com/spring/spring-autowiring-by-type/

Big o notation questions

What on earth is Big O?

Big O is the way of measuring the efficiency of an algorithm and how well it scales based on the size of the dataset.  Imagine you have a list of 10 objects, and you want to sort them in order.  There’s a whole bunch of algorithms you can use to make that happen, but not all algorithms are built equal.  Some are quicker than others but more importantly the speed of an algorithm can vary depending on how many items it’s dealing with. Big O is a way of measuring how an algorithm scales.  Big O references how complex an algorithm is.

Big O is represented using something like O(n).  The O simply denoted we’re talking about big O and you can ignore it (at least for the purpose of the interview).  n is the thing the complexity is in relation to; for programming interview questions this is almost always the size of a collection. The complexity will increase or decrease in accordance with the size of the data store.

Below is a list of the Big O complexities in order of how well they scale relative to the dataset.

O(1)/Constant Complexity: Constant.  This means irrelevant of the size of the data set the algorithm will always take a constant time. 1 item takes 1 second, 10 items takes 1 second, 100 items takes 1 second. It always takes the same amount of time.

O(log n)/Logarithmic Complexity: Not as good as constant, but still pretty good.  The time taken increases with the size of the data set, but not proportionately so. This means the algorithm takes longer per item on smaller datasets relative to larger ones.   1 item takes 1 second, 10 items takes 2 seconds, 100 items takes 3 seconds. If your dataset has 10 items, each item causes 0.2 seconds latency. If your dataset has 100, it only takes 0.03 seconds extra per item. This makes log n algorithms very scalable.

O(n)/Linear Complexity: The larger the data set, the time taken grows proportionately.  1 item takes 1 second, 10 items takes 10 seconds, 100 items takes 100 seconds.

O(n log n): A nice combination of the previous two.  Normally there’s 2 parts to the sort, the first loop is O(n), the second is O(log n), combining to form O(n log n) 1 item takes 2 seconds, 10 items takes 12 seconds, 100 items takes 103 seconds.

O(n^2)/Quadratic Complexity: Things are getting extra slow. 1 item takes 1 second, 10 items takes 100, 100 items takes 10000.  

O(2^n): Exponential Growth! The algorithm takes twice as long for every new element added.  1 item takes 1 second, 10 items takes 1024 seconds, 100 items takes 1267650600228229401496703205376 seconds.

It is important to notice that the above is not ordered by the best to worst complexity. There is no “best” algorithm, as it completely hinges on the size of the dataset and the task at hand.  It is also important to remember the code cost; a more complex algorithm may result in an incredibly quick sort, but if the code has become unmaintainble and difficult to debug is that the right thing to do?  It probably depends on your requirements.

There is also a variation in complexity within the above complexities.  Imagine an algorithm which loops through a list exactly two times.  This would be O(2n) complexity, as it’s going through your lists length (n) twice!

Why does this matter?

Simply put: an algorithm that works on a small dataset is not guaranteed to work well on a large dataset.  Just because something is lightening fast on your machine doesn’t mean that it’s going to work when you scale up to a serious dataset.  You need to understand exactly what your algorithm is doing, and what it’s big O complexity is, in order to choose the right solution.

There are three things we care about with algorithms: best case, worst case and expected case. In reality we only actually care about the latter two, as we’re a bunch of pessimists. If you ask an algorithm to sort a pre-sorted list it’s probably going to do it much faster than a completely jumbled list. Instead we want to know what the worst case (the absolutely maximum amount of steps the algorithm could take) and the expected case (the likely or average number of steps the algorithm could take).  Just to add to the fun, these can and often are different.

Examples

Hopefully you’re with me so far, but let’s dive into some example algorithms for sorting and searching.  The important thing is to be able to explain what complexity an algorithm is.  Interviewers love to get candidates to design algorithms and then ask what the complexity of it is.

O(1)

Irrelevant of the size, it will always return at constant speed. The javadoc for Queue states that it is  “constant time for the retrieval methods (peek, element, and size)”. It’s pretty clear why this is the case.  For peek, we are always returning the first element which we always have a reference to; it doesn’t matter how many elements follow it.  The size of the list is updated upon element addition/removal, and referencing this number is just one operation to access no matter what the size of the list is.

O(log n)

The classic example is a Binary search.  You’re a massive geek so you’ve obviously alphabetised your movie collection. To find your copy of “Back To The Future”, you first go to the middle of the list. You discover the middle film is “Meet The Fockers”, so you then head to the movie in between the start and this film.  You discover this is “Children of Men”. You repeat this again and you’ve found back to the future.   There’s a great interactive demo of binary search here.

Although adding more elements will increase the amount of time it takes to search, it doesn’t do so proportionally. Therefore it is O(log n).

O(n)

As discussed in my post on collections, LinkedLists are not so good (relatively speaking) when it comes to retrieval.  It actually has a Big O of O(n) as in the worst case, to find an element T which is the last element in the list, it is necessary to navigate the entire list of n elements to find T. As the number of elements increases so does the access time in proportion.

O(n log n)

The best example of O(n log n) is a merge sort. This is a divide and conquer algorithm. Imagine you have a list of integers. We divide the list in two again and again until we are left with with a number of lists with 1 item in: each of these lists is therefore sorted.We then merge each list with it’s neighbour (comparing the first elements of each every time). We repeat this with the new composite list until we have our sorted result.(Image from wikipedia)

To explain why this is O(n log n) is a bit more complex.  In the above example of 8 numbers, we have 3 levels of sorting:

• 4 list sorts when the list sizes are 2
• 2 list sorts when the list sizes are 4
• 1 list sort when the list size is 8

Now consider if I were to double the number of elements to 16: this would only require one more level of sorting. Hopefully your recognise this is a log n scale.

However, on each level of sorting a total of n operations takes place (look at the red boxes in the diagram above).  this results in (n * log n) operations, e.g. O(n log n).

O(n^2)

The Bubble Sort algorithm is everyone’s first algorithm in school, and interestingly it is quadratic complexity. If you need a reminder; we go through the list and compare each element with the one next to it, swapping the elements if they are out of order. At the end of the first iteration, we then start again from the beginning, with the caveat that we now know the last element is correct.