When an inner class is created inside a class in java, it transparently contains a reference to its parent class. If by chance this reference leaks out , it compromises the thread safety of the parent class. To avoid these kind of issues , factory methods should be used to create inner classes .
Another thing that should be best avoided is : starting of a thread inside the constructor of a class.
Since the thread object also shares the reference to its parent class, this reference might be in an inconsistent state when the thread is started .
To prevent these type of scenarios factory methods are best.
e.g
public class Prent {
private childThread;
private Parent(){
childThread = new Thread();
}
public static Parent newInstance(){
Parent parent = new Parent();
childThread.start();
return parent
}
}
Sunday, March 09, 2008
Monday, March 03, 2008
Eclipse : Adding nature to a project
In Eclipse plugin development terminology adding a nature to a project is like tagging the project with a specific tag . Generally natures are used to install various builders for the project. I will talk about builders in a later post . Lets look at some code and see how how natures are added to projects:
IProjectDescription projectDescription = project.getDescription();
description is a description of the project . It gives a lot of information including the entire list of
nature ids and build commands.
String[] ids = projectDescription.getNatureIds();
String[] newIds = new String[ids.length + 1];
System.arraycopy(ids,0,newIds,0,ids.length);
newIds[ids.length] = YOUR_NATURE_ID;
projectDescription.setNatureIds(newIds);
project.setDescription(projectDescription,null);
the remove nature id code is kind of similar .
To actually implement your nature , you need to contribute to the extension point
org.eclipse.core.resources.natures
Basically that boils down to adding something like this in your plugin.xml
id="yourNatureID"
name="Your Nature Name">
"id" here represents the id of the nature .
"name" represents the name of the nature .
"class" represents the class implements the IProjectNature .
the requires-nature here represents the nature id that is required for this nature to be successfully installed .
Next , finally the class that implements the IProjectNature interface.
public class YourProjectNature implements IProjectNature {
IProject project;
public YourProjectTestNature() {
}
public IProject getProject() {
return project;
}
public void setProject(IProject project) {
this.project= project;
}
}
IProjectDescription projectDescription = project.getDescription();
description is a description of the project . It gives a lot of information including the entire list of
nature ids and build commands.
String[] ids = projectDescription.getNatureIds();
String[] newIds = new String[ids.length + 1];
System.arraycopy(ids,0,newIds,0,ids.length);
newIds[ids.length] = YOUR_NATURE_ID;
projectDescription.setNatureIds(newIds);
project.setDescription(projectDescription,null);
the remove nature id code is kind of similar .
To actually implement your nature , you need to contribute to the extension point
org.eclipse.core.resources.natures
Basically that boils down to adding something like this in your plugin.xml
name="Your Nature Name">
"id" here represents the id of the nature .
"name" represents the name of the nature .
"class" represents the class implements the IProjectNature .
the requires-nature here represents the nature id that is required for this nature to be successfully installed .
Next , finally the class that implements the IProjectNature interface.
public class YourProjectNature implements IProjectNature {
IProject project;
public YourProjectTestNature() {
}
public IProject getProject() {
return project;
}
public void setProject(IProject project) {
this.project= project;
}
}
Sunday, March 02, 2008
Little Sugar : C++
The only to initialize const pointers in c++ within a class , is via member initialization list.
class MyClass{
Data * const data_ptr;
MyClass(Data * const value) : data_ptr(value)
{}
};
class MyClass{
Data * const data_ptr;
MyClass(Data * const value) : data_ptr(value)
{}
};
Tuesday, February 05, 2008
Remove from Array : Java Quickie
lets say you have a problem . You have an array of N numbers . You want to remove the i th number . Then you need a new array not containing the j th number . You are using java . How can you do it ??
Here 's a quickie:
int[] result = null;
result = new int[n-1];
if(i > 0 ) System.arraycopy(array,0,result,0,i);
if(i+1 < n ) System.arraycopy(array,i+1,result,i,n-1-i);
}
This is quick way of removing the element you need and getting a new array devoid of the removed number .
Here 's a quickie:
int[] result = null;
result = new int[n-1];
if(i > 0 ) System.arraycopy(array,0,result,0,i);
if(i+1 < n ) System.arraycopy(array,i+1,result,i,n-1-i);
}
This is quick way of removing the element you need and getting a new array devoid of the removed number .
Thursday, January 31, 2008
Thnking in Heaps : Algorithms
An interative version of max-Heap :
void iter_maxHeapify(int * a,int rootIndex,int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = left(rootIndex);
for(int largest = rootIndex;
(leftIndex < heapLength) || (rightIndex < heapLength);
leftIndex = left(rootIndex),rightIndex = right(rootIndex)){
if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(rootIndex != largest){
swap(a[largest],a[rootIndex]);
rootIndex = largest;
}
}
}
Building the Heap:
void buildMaxHeap(int * a,int heapLength){
for(int i = heapLength/2;i >=0;i--){
maxHeapify(a,i,heapLength);
}
}
Sorting a heap:
void heapSort(int * a ,int heapLength){
buildMaxHeap(a,heapLength);
for(int i = 0;i < heapLength;i++){
swap(a[i],a[heapLength-1]);
maxHeapify(a,1,heapLength-i-1);
}
}
void iter_maxHeapify(int * a,int rootIndex,int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = left(rootIndex);
for(int largest = rootIndex;
(leftIndex < heapLength) || (rightIndex < heapLength);
leftIndex = left(rootIndex),rightIndex = right(rootIndex)){
if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(rootIndex != largest){
swap(a[largest],a[rootIndex]);
rootIndex = largest;
}
}
}
Building the Heap:
void buildMaxHeap(int * a,int heapLength){
for(int i = heapLength/2;i >=0;i--){
maxHeapify(a,i,heapLength);
}
}
Sorting a heap:
void heapSort(int * a ,int heapLength){
buildMaxHeap(a,heapLength);
for(int i = 0;i < heapLength;i++){
swap(a[i],a[heapLength-1]);
maxHeapify(a,1,heapLength-i-1);
}
}
Tweaking JDT : eclipse
To create a new Java Class/Interface using JDT you can use the following code :
IJavaproject prj;
IPackage package;
prj.createType(package, "your class body");
To find subclasses of a given type using JDT use :
IType type = prj.findType("class name");
ITypeHierarchy typeHierarchy = type.newTypeHierarchy(prj,new NullProgressMonitor());
IType[] subclasses = typeHierarchy.getAllSubtypes(prj);
To check if the given class aka IType is part of this project
IType type;
IResource resource = type.getUnderlyingResource();
boolean isPartOfClass = resource.getProject().equals(project.getProject());
IJavaproject prj;
IPackage package;
prj.createType(package, "your class body");
To find subclasses of a given type using JDT use :
IType type = prj.findType("class name");
ITypeHierarchy typeHierarchy = type.newTypeHierarchy(prj,new NullProgressMonitor());
IType[] subclasses = typeHierarchy.getAllSubtypes(prj);
To check if the given class aka IType is part of this project
IType type;
IResource resource = type.getUnderlyingResource();
boolean isPartOfClass = resource.getProject().equals(project.getProject());
Marker Resolutions for markers : Eclipse
In Eclipse it is possible to associate marker resolutions with markers . This is more commonly known as Quick Fixes also evoked by using the key combination Ctrl + 1.
You need to implement the extension point with id :
"org.eclipse.ui.markerResolution"
for the markerType attribute under that extension point specify the marker id
you want to associate this resolution with .
Then in the "class" attribute specify the class that implements the MarkerResolutionGenerator
You need to implement the extension point with id :
"org.eclipse.ui.markerResolution"
for the markerType attribute under that extension point specify the marker id
you want to associate this resolution with .
Then in the "class" attribute specify the class that implements the MarkerResolutionGenerator
The world of wide characters aka Unicode
Wide characters aka unicode characters are characters that occupy 16 bits per character .
In C we have a header file specifically for that .
that contains special data type for that
wchar_t
wchar_t * text = L"Hello";
is used to tell the compiler that it should use 16 bit aka wide variants of characters.
strlen for wide characters becomes wcslen .
To take care of these problems windows provides TCHAR.H
it contains many functions starting with _t , like. ..
_tprintf
by defining _UNICODE
like
#define _UNICODE
its possible to use 16 bit / 8 bit versions of functions without much verbosity .
the same _t functions then correctly map on to their 8 bit and 16 bit counter parts.
In C we have a header file specifically for that .
that contains special data type for that
wchar_t
wchar_t * text = L"Hello";
is used to tell the compiler that it should use 16 bit aka wide variants of characters.
strlen for wide characters becomes wcslen .
To take care of these problems windows provides TCHAR.H
it contains many functions starting with _t , like. ..
_tprintf
by defining _UNICODE
like
#define _UNICODE
its possible to use 16 bit / 8 bit versions of functions without much verbosity .
the same _t functions then correctly map on to their 8 bit and 16 bit counter parts.
Monday, January 28, 2008
Fnding markers in a workspace : eclipse
If you have a marker or you know a marker id :
let the id be : org.my.marker
then all markers of that type can be easily found . The way to found those markers is :
IWorkspaceRoot root = ResourcePlugin.getWorkspace().getRoot();
root.findMarkers("org.my.marker",false,IResource.DEPTH_INFINITE);
To create a marker :
getProject().createMarker("org.my.marker",false,IResource.DEPTH_INFINITE);
generally since workspace changes are expensive , an IWorkspaceRunnable should be used
to batch many workspace operations together .
IWorkspaceRunnable runnable = new IWorkspaceRunnable(){
public void run(IProgressMonitor monitor) {
IMarker marker = resource.createMarker(markerId);
setAttributes(marker);
}
};
the setAttributes method sets the marker . This generally boild down to populating a hashtable
and setting it .
resource.getWorkspace().run(runnable , null);
An imageProvider can be specified in the marker definition to define an image for the marker .
let the id be : org.my.marker
then all markers of that type can be easily found . The way to found those markers is :
IWorkspaceRoot root = ResourcePlugin.getWorkspace().getRoot();
root.findMarkers("org.my.marker",false,IResource.DEPTH_INFINITE);
To create a marker :
getProject().createMarker("org.my.marker",false,IResource.DEPTH_INFINITE);
generally since workspace changes are expensive , an IWorkspaceRunnable should be used
to batch many workspace operations together .
IWorkspaceRunnable runnable = new IWorkspaceRunnable(){
public void run(IProgressMonitor monitor) {
IMarker marker = resource.createMarker(markerId);
setAttributes(marker);
}
};
the setAttributes method sets the marker . This generally boild down to populating a hashtable
and setting it .
resource.getWorkspace().run(runnable , null);
An imageProvider can be specified in the marker definition to define an image for the marker .
Sunday, January 27, 2008
Overloading the && , || , " , " operators : C++
&& , || and comma operator in C++ are very useful . && and || are useful in short circuiting code .
Now when you overload these operator at the global level or at the member level . Then at that case
an expression like
(exp1 && exp2)
gets transformed into something like
(exp1.operator&&(exp2))
that being the case , both the arguments exp1 and exp2 are evaluated . Hence since we are not
sure in which order the arguments are evaluated , short circuiting is thrown out of the window.
So commonsense says it makes sense not to overload the && , || and the comma operator .
Now when you overload these operator at the global level or at the member level . Then at that case
an expression like
(exp1 && exp2)
gets transformed into something like
(exp1.operator&&(exp2))
that being the case , both the arguments exp1 and exp2 are evaluated . Hence since we are not
sure in which order the arguments are evaluated , short circuiting is thrown out of the window.
So commonsense says it makes sense not to overload the && , || and the comma operator .
Friday, January 25, 2008
Little Sugar (Trees : relations)
A complete binary tree has odd number of nodes .
Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree
The number of internal nodes + 1 = number of leaves
number of internal nodes = number of leaves - 1
n = number of nodes
n = number of leaves + number of internal nodes
n +1 = 2 * number of leaves
number of leaves = (n+1)/2
The number of total nodes upto height h :
= pow(2,h+1) - 1
The number of nodes for any binary tree at height (h) :
= ceil(n / pow(2,h+1))
Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree
The number of internal nodes + 1 = number of leaves
number of internal nodes = number of leaves - 1
n = number of nodes
n = number of leaves + number of internal nodes
n +1 = 2 * number of leaves
number of leaves = (n+1)/2
The number of total nodes upto height h :
= pow(2,h+1) - 1
The number of nodes for any binary tree at height (h) :
= ceil(n / pow(2,h+1))
Little Sugar (Trees : relations)
A complete binary tree has odd number of nodes .
Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree
The number of internal nodes + 1 = number of leaves
number of internal nodes = number of leaves - 1
n = number of nodes
n = number of leaves + number of internal nodes
n +1 = 2 * number of leaves
number of leaves = (n+1)/2
Number of leaves + number of internal nodes ( both even) +
1 = number of nodes in a tree
The number of internal nodes + 1 = number of leaves
number of internal nodes = number of leaves - 1
n = number of nodes
n = number of leaves + number of internal nodes
n +1 = 2 * number of leaves
number of leaves = (n+1)/2
Sunday, January 20, 2008
type conversions : C++
Implicit type conversions in C++ can be quite problematic . To take care of type conversion issues , C++ provides us with a simple mechanism .
use the explicit keyword .
so for a class like Array
class Array{
public:
explicit Array(int size){
...
}
};
so by using the explicit keyword in this manner , you tell the compiler to use the constructor only
when explicit object construction is taking place.
another way around the explicit keyword is :
class Array{
public:
class ArraySize{
public:
ArraySize(int size)
this->size = size;
}
private:
int size;
};
Array(ArraySize size){
...
}
};
So by using the nested public ArraySize class in this manner , you 'll see that even if the compiler makes implicit type conversions for cases like
Array a(10);
the integer 10 is correctly transformed to ArraySize and the constructor having ArraySize as a parameter is called .
The beauty of this last technique is that it works in many cases , cause the compiler is allowed to make 1 implicit type conversion but now two.
use the explicit keyword .
so for a class like Array
class Array{
public:
explicit Array(int size){
...
}
};
so by using the explicit keyword in this manner , you tell the compiler to use the constructor only
when explicit object construction is taking place.
another way around the explicit keyword is :
class Array{
public:
class ArraySize{
public:
ArraySize(int size)
this->size = size;
}
private:
int size;
};
Array(ArraySize size){
...
}
};
So by using the nested public ArraySize class in this manner , you 'll see that even if the compiler makes implicit type conversions for cases like
Array a(10);
the integer 10 is correctly transformed to ArraySize and the constructor having ArraySize as a parameter is called .
The beauty of this last technique is that it works in many cases , cause the compiler is allowed to make 1 implicit type conversion but now two.
Tuesday, January 15, 2008
Default Constructors : C++
Just imagine if your class does not have a default constructor and infact has one that accepts a parameter . In that case few things might not be possible . To illustrate
class Piece{
public:
Piece(int n);
};
Things like these will not work
Piece pieces[10];
Why?? -> cause u don t have a default constructor and trying to create an array of 10 piece instances just tries to call exactly that for every one of them .
Piece * pieces = new Piece[10];
wont work.
How to get it working :
Piece pieces[] = {
Piece(1),
Piece(2),
Piece(3)
};
Another way to get it working would be :
Piece * pieces[10];
: here you are just declaring an array of 10 Piece pointers;
Or Piece* *pieces = new Piece*[10];
But you still need to initialize all the pointers like this :
for(int i = 0;i < 10;i++){ pieces[i] = new Piece(i); }
Another way of initializing accomplishing this would be :
void * memory = operator new[](10 * sizeof(Piece));
this will create memory for 10 piece objects . Now we can go an and make the memory more specific to Piece :
Piece * pieces = static_cast<piece*>(memory);
Now that pieces points to memory for Piece , lets initialize the pieces with code like
for(int i = 0;i < 10;i++){ new(&pieces[i]) Pieces(i); }
Though this arcane technique will get the job done . It seriously is arcane . Not only that it also has the disadvantage of boilerplate code like this :
for(int i = 9;i >= 0;i--){
pieces[i].~Piece();
}
operator delete[] memory;
If we do not follow the 1st approach , we see that what problems we can face . A small hack to get around this problem would be :
class Piece{
public:
Piece(int n = Piece::UNDEFINED);
private:
static const int UNDEFINED;
};
const int Piece::UNDEFINED = -1;
class Piece{
public:
Piece(int n);
};
Things like these will not work
Piece pieces[10];
Why?? -> cause u don t have a default constructor and trying to create an array of 10 piece instances just tries to call exactly that for every one of them .
Piece * pieces = new Piece[10];
wont work.
How to get it working :
Piece pieces[] = {
Piece(1),
Piece(2),
Piece(3)
};
Another way to get it working would be :
Piece * pieces[10];
: here you are just declaring an array of 10 Piece pointers;
Or Piece* *pieces = new Piece*[10];
But you still need to initialize all the pointers like this :
for(int i = 0;i < 10;i++){ pieces[i] = new Piece(i); }
Another way of initializing accomplishing this would be :
void * memory = operator new[](10 * sizeof(Piece));
this will create memory for 10 piece objects . Now we can go an and make the memory more specific to Piece :
Piece * pieces = static_cast<piece*>(memory);
Now that pieces points to memory for Piece , lets initialize the pieces with code like
for(int i = 0;i < 10;i++){ new(&pieces[i]) Pieces(i); }
Though this arcane technique will get the job done . It seriously is arcane . Not only that it also has the disadvantage of boilerplate code like this :
for(int i = 9;i >= 0;i--){
pieces[i].~Piece();
}
operator delete[] memory;
If we do not follow the 1st approach , we see that what problems we can face . A small hack to get around this problem would be :
class Piece{
public:
Piece(int n = Piece::UNDEFINED);
private:
static const int UNDEFINED;
};
const int Piece::UNDEFINED = -1;
Hello Windows Facts
windows.h is the mother of all other header files in windows . It includes other header files .
Windef.h => basic type defintions
winnt.h => type definitions for unicode support.
winbase.h => kernel functions.
winusr.h => user interface functions
wingdi.h => graphics device interface functions.
WINAPI => is a naming convention like __stdcall .
Windef.h => basic type defintions
winnt.h => type definitions for unicode support.
winbase.h => kernel functions.
winusr.h => user interface functions
wingdi.h => graphics device interface functions.
WINAPI => is a naming convention like __stdcall .
Moving Patterns
If you have a layer of objects and each object in that layer shares a certain set of methods . Those methods can be moved in a common super type . This super type that is common for a whole layer is called a layer super type .
Remote Facade is a facade for objects that are not part of a given process address space , in other words whenever you need to access objects that line in other processes you should use a remote facade to encapsulate and operate on remote objects via the facade . The facade make a number of operation invisible and may also cache the most commonly use objects.
When ever data has to marshaled across processes boundaries and lot of data needs to sent . A Data Transfer Object can be used . The parameters are packed into a simple POJO called a DTO and marshaled . On the server side , the server used some sort of assembler to break the DTO and set the corresponding properties on domain objects.
Remote Facade is a facade for objects that are not part of a given process address space , in other words whenever you need to access objects that line in other processes you should use a remote facade to encapsulate and operate on remote objects via the facade . The facade make a number of operation invisible and may also cache the most commonly use objects.
When ever data has to marshaled across processes boundaries and lot of data needs to sent . A Data Transfer Object can be used . The parameters are packed into a simple POJO called a DTO and marshaled . On the server side , the server used some sort of assembler to break the DTO and set the corresponding properties on domain objects.
Friday, January 11, 2008
Floating in a Tree
If you have a priority queue setup of many nodes. Lets say we want to bring the node with the highest value to the top . IN orther words if i have given a heap than how do i modify the heap so that the biggest element is always present at the root.
One simple logic can be . Given a root node of a subtree .
void maxHeapify(int * a,int rootIndex, int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = right(rootIndex);
if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(largest != rootIndex){
swap(a[largest],a[rootIndex]);
maxHeapify(a,largest,heapLength);
}
}
The worst case time for floating a node to any another node depending on your optimization would be approximately equal to the height of the tree , which would generally result in something like ~ lg(N) . To give a counter example for a max Heap operating in a heap . lets give a value of 0 to the root , and let all the other nodes be 1 . In that case the program would go all the way down the heap till the last leaf .
One simple logic can be . Given a root node of a subtree .
- Assume the root node is the largest node .
- Now compare the value of root node with left child and mark the one with the bigger value as biggest
- Then compare biggest with the right child now and make the bigger of the two as the new biggest.
- now repeat the above mentioned steps with the new largest node
void maxHeapify(int * a,int rootIndex, int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = right(rootIndex);
if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(largest != rootIndex){
swap(a[largest],a[rootIndex]);
maxHeapify(a,largest,heapLength);
}
}
The worst case time for floating a node to any another node depending on your optimization would be approximately equal to the height of the tree , which would generally result in something like ~ lg(N) . To give a counter example for a max Heap operating in a heap . lets give a value of 0 to the root , and let all the other nodes be 1 . In that case the program would go all the way down the heap till the last leaf .
Thursday, January 10, 2008
casts in C++
C++ provides us with 4 types of casting mechanisms . Namely:
In C casting is done via () operator
int i = 7;
e.g double d = (double) i;
in c++ to do something like this one should use static_cast .
e.g double d = static_cast<double>(i);
const_cast
const_cast is used to remove constness of an object .
jump(Person * person);
Person p;
const Person& constPerson = p;
then some thing like this wont work.
jump(&constPerson) , cause jump expects a non const object . To fix this you would have to use something like this.
jump(const_cast<person*>(&constPerson));
dynamic_cast
This cast is used with inheritance hierarchies . Say to cast a between pointers or references of base classes to references or pointers of derived classes.
e.g
Mammal * mammal;
jump(dynamic_cast<person*>(mammal));
if there was a function like
jump(Person& person); then
we would have something like
jump(dynamic_cast<person&>(*mammal));
if the casting is not possible , the dynamic_cast mechaism throws an excetion or the result is null (This is implementation specific)
- static_cast
- const_cast
- dynamic_cast
- reinterpret_cast
In C casting is done via () operator
int i = 7;
e.g double d = (double) i;
in c++ to do something like this one should use static_cast .
e.g double d = static_cast<double>(i);
const_cast
const_cast is used to remove constness of an object .
jump(Person * person);
Person p;
const Person& constPerson = p;
then some thing like this wont work.
jump(&constPerson) , cause jump expects a non const object . To fix this you would have to use something like this.
jump(const_cast<person*>(&constPerson));
dynamic_cast
This cast is used with inheritance hierarchies . Say to cast a between pointers or references of base classes to references or pointers of derived classes.
e.g
Mammal * mammal;
jump(dynamic_cast<person*>(mammal));
if there was a function like
jump(Person& person); then
we would have something like
jump(dynamic_cast<person&>(*mammal));
if the casting is not possible , the dynamic_cast mechaism throws an excetion or the result is null (This is implementation specific)
Wednesday, January 09, 2008
Little Sugar: C++ references
C++ references are a variant of const pointers that always point to something .
Now consider
string s1("abc");
string s2("def");
string & refTos1 = s1;
Now refTosi points to s1.
Even after refTos1 = s2. Its still points to s1 . But the value of s1 is now changed from "abc" to "def"
Now consider
string s1("abc");
string s2("def");
string & refTos1 = s1;
Now refTosi points to s1.
Even after refTos1 = s2. Its still points to s1 . But the value of s1 is now changed from "abc" to "def"
Tuesday, January 08, 2008
Little Sugar : Big Oh
Consider a scenario where you had a list of N numbers . Now say you have an algorithm that finds the does some sort of comparison . If comparison strategy used compares every element with all the succeeding elements . Then on an average the number of comparisons possible in different cases would be something like this :
(n) + (n-1) + (n-2) .... 1
for the 1 st case we have n comparisons
for the 1 st element we have n-1 comparisons
for the 2 nd element we have n-2 comparison .. and so on.
the sum is = ((n)*(n+1))/2 = O(n^2)
(n) + (n-1) + (n-2) .... 1
for the 1 st case we have n comparisons
for the 1 st element we have n-1 comparisons
for the 2 nd element we have n-2 comparison .. and so on.
the sum is = ((n)*(n+1))/2 = O(n^2)
Subscribe to:
Posts (Atom)
Labels
. linux
(1)
algorithm
(15)
analytics
(1)
bash
(2)
bigoh
(1)
bruteforce
(1)
c#
(1)
c++
(40)
collections
(1)
commands
(2)
const
(1)
cosine similarity
(1)
creating projects
(1)
daemon
(1)
device_drivers
(1)
eclipse
(6)
eclipse-plugin-development
(9)
equals
(1)
formatting
(1)
freebsd
(1)
game programming
(1)
hashcode
(1)
heap
(1)
heaps
(1)
immutable-objects
(1)
java
(19)
JDT
(1)
kernel
(1)
linux
(4)
little sugar
(23)
logging
(1)
machine learning
(1)
marker-resolution
(1)
markers
(1)
mergesort
(1)
mixins
(1)
numbers
(1)
opengl
(2)
patterns
(2)
priority-queue
(1)
programming
(51)
ps
(1)
ranking
(1)
refactoring
(3)
references
(1)
security
(1)
set
(1)
shell
(1)
similarity
(1)
statistics
(1)
stl
(1)
tetris
(1)
threads
(1)
trees
(2)
unicode
(1)
unix
(2)
views
(2)
windows programming
(2)
XNA
(1)