Running time of sorting algorithm

Question

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;
    }

why for(int i=0;i<4;i++) ? this means that your array will always have 4 elementd? — jsalatas
– jsalatas, Commented Dec 9, 2016 at 6:56
Yes, it appears to be O(n^2), assuming that your loops intend to iterate over the full length of the SortTime object/collection. — Tim Biegeleisen
– Tim Biegeleisen, Commented Dec 9, 2016 at 6:56
Better ;-) another code review hint: you have duplicated that "swapping" code three times. In real life, you would want to put that into a little helper method! Code duplication is one of the roots of evil! — GhostCat
– GhostCat, Commented Dec 9, 2016 at 17:26

square1001 · Accepted Answer · 2016-12-09 07:01:11Z

4

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.

answered Dec 9, 2016 at 7:01

square1001

1,46213 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Yousaf Over a year ago

thanks for your response. +1 for simple explanation.

patrik Over a year ago

Worth mentioning is that the O(n) notation applies when n is large, so limit theory can be applied. When n->Inf, then O(n^2-2n+1) ->O(n^2).

Collectives™ on Stack Overflow

Running time of sorting algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related