CODEWITHSUNDEEP
javaalgorithmbig-o
Yousaf
Yousaf

Reputation: 29282

Running time of sorting algorithm

I have written a function to sort time stamps (hh:mm:ss) in order from oldest to newest. I am interested in knowing the approximate worst case running time of my code but i don't know how to determine that.

My rough guess is O(n-1)^2 because of nested for loop. Am i correct ?

If not, then can someone determine what would be the approximate running time of my code in Big O notation ? 

public void sortTimeStamp(SortTime timestamps[])
{
    for(int i=0;i<timestamps.length-1;i++)
    {
        for(int j=0;j<timestamps.length-1;j++)
        {
            if(timestamps[j].hour > timestamps[j+1].hour)
            {
                swap_timestamps(timestamps, j);
            }
            else
            if(timestamps[j].hour == timestamps[j+1].hour)
            {
                if(timestamps[j].minutes > timestamps[j+1].minutes)
                {
                     swap_timestamps(timestamps, j);
                }
                else
                if(timestamps[j].minutes == timestamps[j+1].minutes && timestamps[j].seconds > timestamps[j+1].seconds)
                {
                    swap_timestamps(timestamps, j);
                }

            }
        }
    }
}

Swap function

public void swap_timestamps(SortTime timestamps[], int index)
    {
        SortTime temp = timestamps[index];
        timestamps[index] = timestamps[index+1];
        timestamps[index+1] = temp;
    }

Upvotes: 0

Views: 126

Answers (1)

square1001
square1001

Reputation: 1464

I think this sorting algorithm is O(n^2).
Your answer is O((n-1)^2), and it is equal to O(n^2-2n+1).
But the big-O notation O(f(n)) means "the time is approximately proportional for f(n)" (not exactly correct, but it's easy to understand)
So you don't have to think -2n or 1 term.
You can only think about n^2 term, and you don't need any coefficients.

But you can do mergesort and the time complexity is O(n log n)
Counting sort is OK because hh:mm:ss can express only 86400 ways. It accomplish O(n+k) where k=86400.

Upvotes: 4

Related Questions