What is Time Complexity of An algorithm? : (O-notation)

The performance of a data structure depends on many factors such as efficiency of the code, the hardware configuration etc. Generally all the factors are calculated and put in the form of a mathematical expression. For example suppose for a particular sorting technique the running time is given by

2N2 + 18.7N + 5

where N is the number of elements being sorted.

But if the efficiency is described in this way, it’s a bit difficult to compare the respective time complexities for different algorithm. Therefore, in order to make our task easier, O-notation (Pronounced as “big-oh notation”) is used. O-notation is a generalization of the complicated expression we get for the time complexity of a particular algorithm. In the above example, with the increase in the number of elements, i.e. N, the N2 term becomes significant enough to neglect the rest lower power terms of N. The O-notation in this case is therefore, O(N2). This means, if the number of elements increases by two fold, the time taken increases approximately by four fold in this case.

As we need to know the time complexity mainly to compare two algorithms, so the O-notation technique (even it is an approximate one) proves to be very useful for this purpose.

Some commonly used O-notations with there meaning are given below.

O(…)

Effect on the running time

if N is doubled

Example algorithm

1

unchanged

Insertion into a Hash table

Log N

Increases by a constant amount

Insertion into a Tree

N

doubled

Linear Search

N log N

Doubled plus a constant amount

Merge sort

N2

Increases fourfold

Bubble sort

Article Written By:
Kamlesh

Reference:

Generics and Collections in Java 5 – Mauris Naftalin & Philip Wadler

Advertisements

About JVM and JRE

[I Got Stuck!:37]
By Shankar

Inside Java :
The Java Virtual Machine
By David Reilly

At the heart of the Java platform lies the Java Virtual Machine, or JVM. Most programming languages compile source code directly into machine code, suitable for execution on a particular microprocessor architecture. The difference with Java is that it uses bytecode – a special type of machine code.

Java bytecode executes on a special type of microprocessor. Strangely enough, there wasn’t a hardware implementation of this microprocessor available when Java was first released. Instead, the processor architecture is emulated by what is known as a “virtual machine”. This virtual machine is an emulation of a real Java processor – a machine within a machine (Figure One). The only difference is that the virtual machine isn’t running on a CPU – it is being emulated on the CPU of the host machine.

The Java Virtual Machine is responsible for interpreting Java bytecode, and translating this into actions or operating system calls.
For example, a request to establish a socket connection to a remote machine will involve an operating system call. Different operating systems handle sockets in different ways – but the programmer doesn’t need to worry about such details. It is the responsibility of the JVM to handle these translations, so that the operating system and CPU architecture on which Java software is running is completely irrelevant to the developer.

The Java Virtual Machine forms part of a large system, the Java Runtime Environment (JRE). Each operating system and CPU architecture requires a different JRE. The JRE comprises a set of base classes, which are an implementation of the base Java API, as well as a JVM.
The portability of Java comes from implementations on a variety of CPUs and architectures. Without an available JRE for a given environment, it is impossible to run Java software.

Differences between JVM implementations
Though implementations of Java Virtual Machines are designed to be compatible, no two JVMs are exactly alike. For example, garbage collection algorithms vary between one JVM and another, so it becomes impossible to know exactly when memory will be reclaimed. The thread scheduling algorithms are different between one JVM and another (based in part on the underlying operating system), so that it is impossible to accurately predict when one thread will be executed over another.

Initially, this is a cause for concern from programmers new to the Java language. However, it actually has very little practical bearing on Java development. Such predictions are often dangerous to make, as thread scheduling and memory usage will vary between different hardware environments anyway. The power of Java comes from not being specific about the operating system and CPU architecture – to do so reduces the portability of software.

Summary
The Java Virtual Machine provides a platform-independent way of executing code, by abstracting the differences between operating systems and CPU architectures. Java Runtime Environments are available for a wide variety of hardware and software combinations, making Java a very portable language. Programmers can concentrate on writing software, without having to be concerned with how or where it will run. The idea of virtual machines is nothing new, but Java is the most widely used virtual machine used today. Thanks to the JVM, the dream of Write Once-Run Anywhere (WORA) software has become a reality.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[I Got Stuck!:35]
By Alok

  • Byte code is a highly optimized set of instructions. JVM is an interpreter for byte code. Translating a java program into byte code helps makes it much easier to run a program in a wide variety of environment.
  • JVM is an interpreter for byte code
  • JIT (Just In Time) is a part of JVM, it compiles byte code into executable code in real time, will increase the performance of the interpretations.
  • JRE is an implementation of the Java Virtual Machine, which actually executes Java programs.
  • à JDK is bundle of software that you can use to develop Java based software, Tools provided by JDK are

(i) javac – compiler (ii) java – interpretor (iii) jdb – debugger (iv) javap – Disassembles
(v) appletviewer – Applets (vi) javadoc – documentation generator (vii) javah – ‘C’ header file generator