# Thread: Time Complexity Java Code?

1. Member
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.

2. Member
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 big-O 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 right-most 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.

3. Member
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

4. Originally Posted by sky
\the worst cases are:

QuickSort O(n log n)
That is not true for a naive quicksort implementation; read this linkfor an explanation of its O(n^2) behaviour.

kind regards,

Jos

5. Member
Join Date
Nov 2009
Posts
96
Rep Power
0
Originally Posted by JosAH
That is not true for a naive quicksort implementation; read this linkfor an explanation of its O(n^2) behaviour.

kind regards,

Jos
I know, it depends on the choice for the pivot, but I was talking about the standart implementation.

Originally Posted by Lyricid
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
Easy: you have to run your algorithm using as an input an array for which the algorithms runs in its best, average and worst case.

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...,n-1,n]
-Average case: Running the algorithm with a random array it should be enough.
.Worst case: Run the algorithm with the array [n, n-1, ....1, 0]

6. Member
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!

7. Member
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.length-i;
}```
If you don't want to overwrite the array, there are many possibilities. If your method for the algorithm is InsertionSort(array), you can create a new method called :

Java Code:
```InsertionSortBestCase() {
//Create a sorted array
//Call InsertionSort(array)
}```

8. Originally Posted by sky
I know, it depends on the choice for the pivot, but I was talking about the standart implementation.
Even then: a clever pivot selection tries to minimize the chance for O(n^2) behavour but it can't always avoid it.

kind regards,

Jos

9. Member
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.length-i;
}
my code already contains this piece of code, but i cant seem to get it to display best case worst case and average case

all i can display is the running time in nanoseconds

10. Originally Posted by Lyricid
my code already contains this piece of code, but i cant seem to get it to display best case worst case and average case

all i can display is the running time in nanoseconds
Count the number of comparisons and swaps needed in your sorting routine. Timing wall clock time is useless in Java for small, short runs because of the hotspot mechanism and associated JIT compilation.

kind regards,

Jos

11. Member
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..

12. Member
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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•