Results 1 to 12 of 12
  1. #1
    Lyricid is offline Member
    Join Date
    Nov 2009
    Posts
    28
    Rep Power
    0

    Exclamation 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!

  2. #2
    sky
    sky is offline Member
    Join Date
    Nov 2009
    Posts
    96
    Rep Power
    0

    Default

    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. #3
    Lyricid is offline Member
    Join Date
    Nov 2009
    Posts
    28
    Rep Power
    0

    Default

    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. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sky View Post
    \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. #5
    sky
    sky is offline Member
    Join Date
    Nov 2009
    Posts
    96
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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.

    Quote 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. #6
    Lyricid is offline Member
    Join Date
    Nov 2009
    Posts
    28
    Rep Power
    0

    Default

    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. #7
    sky
    sky is offline Member
    Join Date
    Nov 2009
    Posts
    96
    Rep Power
    0

    Default

    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. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by sky View Post
    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. #9
    Lyricid is offline Member
    Join Date
    Nov 2009
    Posts
    28
    Rep Power
    0

    Default

    // 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. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by Lyricid View Post
    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. #11
    nextkit is offline Member
    Join Date
    Nov 2009
    Posts
    1
    Rep Power
    0

    Default

    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. #12
    Lyricid is offline Member
    Join Date
    Nov 2009
    Posts
    28
    Rep Power
    0

    Exclamation 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
    Attached Files Attached Files

Similar Threads

  1. Time complexity - foor loop
    By hawaiifiver in forum New To Java
    Replies: 5
    Last Post: 02-05-2011, 04:06 PM
  2. complexity issue!!
    By deepa8400 in forum New To Java
    Replies: 4
    Last Post: 08-25-2009, 04:25 AM
  3. Replies: 2
    Last Post: 02-17-2009, 03:20 PM
  4. Replies: 2
    Last Post: 11-04-2008, 02:48 AM
  5. Singleton considered stupid, Java and complexity
    By fishtoprecords in forum Forum Lobby
    Replies: 11
    Last Post: 07-06-2008, 03:38 AM

Posting Permissions

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