Results 1 to 12 of 12
Thread: Time Complexity Java Code?
 12072009, 04:55 PM #1Member
 Join Date
 Nov 2009
 Posts
 28
 Rep Power
 0
Time Complexity Java Code?
can anyone give me a time complexity java code for the best case worst case and average case of sorting algorithms i have created the following algorithms
Merge Sort
Quick Sort
Binary Search
Insertion Sort
all of them return the running time of the algorithm but i need a code that will show me the best case worst case and average case of the algorithm any ideas, i have exhausted google but no luck.
thanks in advance!
 12072009, 05:04 PM #2Member
 Join Date
 Nov 2009
 Posts
 96
 Rep Power
 0
First of all, the complexity of an algorithm does not depend on the programming language. In bigO notation, the complexity for those algorithms can be found in the Wikipedia. If I don't remember bad, the worst cases are:
Insertion Sort O(n^2)
MergeSort O(n log n)
QuickSort O(n log n)
Binary Search O(log n)
If you need some code to show the worst case, the only thing you have to do is enter an especific input depending on the algorithm. For example, in InsertionSort (because of its logic) the worst case is achieved when the array to sort is sorted in transverse order. From Wikipedia:
The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). During each iteration, the first remaining element of the input is only compared with the rightmost element of the sorted subsection of the array.
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n2)).
The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting arrays containing fewer than ten elements.
There is too many theoretical things behind that so again, read the wikipedia for that.
 12072009, 05:10 PM #3Member
 Join Date
 Nov 2009
 Posts
 28
 Rep Power
 0
i understand the concept of time complexity but i need a piece of code that shows,
the best case , the worst case, and the average case in nanoseconds of my algorithm
 12072009, 05:11 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,651
 Blog Entries
 7
 Rep Power
 21
That is not true for a naive quicksort implementation; read this linkfor an explanation of its O(n^2) behaviour.
kind regards,
Jos
 12072009, 05:30 PM #5Member
 Join Date
 Nov 2009
 Posts
 96
 Rep Power
 0
I know, it depends on the choice for the pivot, but I was talking about the standart implementation.
Originally Posted by Lyricid
I already told you how to do it with Insertion Sort.
Best case: Run the algorithm with the array [0,1,2,3,4,5,6...,n1,n]
Average case: Running the algorithm with a random array it should be enough.
.Worst case: Run the algorithm with the array [n, n1, ....1, 0]
 12072009, 05:37 PM #6Member
 Join Date
 Nov 2009
 Posts
 28
 Rep Power
 0
i know what you are saying but.....
the algorithms allow the user to specify
the Length of the array
the range of the array
then the array fills with random numbers so therefore i can not have a specific array, hence why i am after a code to show
best case
worst case
average case
i can upload my codes if you would like??
appreciate all the help though!
 12072009, 05:53 PM #7Member
 Join Date
 Nov 2009
 Posts
 96
 Rep Power
 0
Yes you can have an specific array. After the array is generated, you can overwrite it like this:
Java Code:// for the best case of insertion sort for (int i=0 ; i<array.length ; i++) { array[i]=i; } // for the worst case of insertion sort for (int i=0 ; i<array.length ; i++) { array[i]=array.lengthi; }
Java Code:InsertionSortBestCase() { //Create a sorted array //Call InsertionSort(array) }
 12072009, 06:37 PM #8
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,651
 Blog Entries
 7
 Rep Power
 21
 12072009, 09:16 PM #9Member
 Join Date
 Nov 2009
 Posts
 28
 Rep Power
 0
// for the best case of insertion sort
for (int i=0 ; i<array.length ; i++) {
array[i]=i;
}
// for the worst case of insertion sort
for (int i=0 ; i<array.length ; i++) {
array[i]=array.lengthi;
}
all i can display is the running time in nanoseconds
 12072009, 09:25 PM #10
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,651
 Blog Entries
 7
 Rep Power
 21
 12072009, 09:43 PM #11Member
 Join Date
 Nov 2009
 Posts
 1
 Rep Power
 0
can anybody help me with code for my My Paint Application?.....I'm new to java and i'm writing a project on My Paint Application. I would really appreciate it if anyone out here can help me with it..
 12082009, 04:27 PM #12Member
 Join Date
 Nov 2009
 Posts
 28
 Rep Power
 0
Reallly stuck!
im sorry guys ive tried my best to try and implement this and its just not working, i have uploaded one of my code, which is my merge sort, if you run the START class, and do the steps it shows you the running time of the algorithm in nanoseconds, i want to display the best, worst and average case under it, your help is greatly appreciated trust me, many thanks
Similar Threads

Time complexity  foor loop
By hawaiifiver in forum New To JavaReplies: 5Last Post: 02052011, 04:06 PM 
complexity issue!!
By deepa8400 in forum New To JavaReplies: 4Last Post: 08252009, 04:25 AM 
Getting ExceptionInInitializer exception when i am trying to code a time series chart
By neeraj.singh in forum AWT / SwingReplies: 2Last Post: 02172009, 03:20 PM 
Please tell me I am not crazy... Time Complexity (BigO) Question
By Jordan in forum New To JavaReplies: 2Last Post: 11042008, 02:48 AM 
Singleton considered stupid, Java and complexity
By fishtoprecords in forum Forum LobbyReplies: 11Last Post: 07062008, 03:38 AM
Bookmarks