How do I demonstrate the following algorithm has O(nlogn) time complexity

Question

It's an algorithm that finds the mininum number of descending rows and the rows themselves of an array in O(nlogn) time complexity . Another part of the exercise is to use these descending rows to implement Patience Sort, which also has to be O(nlogn) (that is from the c = 1 part). What I don't get is where the logn part comes from in both cases.

#include <iostream>
#include <fstream>
#include <list>
using namespace std;

ifstream f("data.in");

int main()
{
    int n, v[100];
    f >> n;
    for (int i = 0; i < n; i++)
        f >> v[i];
    list<int> aux;
    aux.push_back(v[0]);
    list<list<int> > rows;
    rows.push_back(aux);
    for (int i = 1; i < n; i++)
    {
        int selected = 0;
        for (list<list<int> >::iterator it = rows.begin(); it != rows.end(); it++)
        {
            if (it->back() > v[i])
            {
                it->push_back(v[i]);
                selected = 1;
                break;
            }
        }
        if (!selected)
        {
            list<int> aux;
            aux.push_back(v[i]);
            rows.push_back(aux);
        }

    }
    for (list<list<int> >::iterator it = rows.begin(); it != rows.end(); it++)
    {
        for (list<int>:: iterator it2 = it->begin(); it2 != it->end(); it2++)
            cout << *it2 << " ";
        cout << endl;
    }

    int c = 1;
    if (c == 1)
    {
        int s[100];
        for (int i = 0; i < n; i++)
        {
            list<list<int> >::iterator it = rows.begin();
            int minim = it->back();
            it++;
            while (it != rows.end())
            {
                if (!it->empty())
                    if (it->back() < minim)
                        minim = it->back();
                it++;
            }
            it = rows.begin();
            while (it != rows.end())
            {
                    if (it->back() == minim)
                    {
                        it->pop_back();
                        if (it->empty())
                            rows.erase(it);
                        break;
                    }
                it++;
            }
            s[i] = minim;
        }
        for (int i = 0; i < n; i++)
            cout << s[i] << " ";

    }

}

I think it's `O(n^2)`? just consider a increasing input sequence. — apple apple, Oct 21 '19 at 14:45
To add to apple apple's comment: Both parts of your code can be *improved* to be O(n log n). That's probably what your instructor is asking for. — ruakh, Oct 21 '19 at 15:16

Eirik Moseng · Answer 1 · 2019-10-23T13:21:53.730

Your outer loops process each piece of input data so the growth is linear, e.g. O(n). Your inner loops only process a smaller subset of the full input data and the growth is logarithmic, e.g. O(log n). Hence the growth is linearithmic, e.g. O(nlogn). If the inner loop processed each piece of input data, the growth would be quadratic, e.g. O(n^2)

A good explanation can be found here:

What does O(log n) mean exactly?

EDIT: My mistake. I agree with the comments under the original post that the growth of the program seems to be O(n^2). I was a little bit quick in the turns. On a quick peek, it looked to me initially that the innerloops were executed log n times. But it looks like that is not the case for the inner loops in the second n iterations. However, as far as I understand the first innerloop seems to me to be executed log n times (so the order of the growth in sorting the rows is O(nlogn)), but maybe I am mistaken.

How do I demonstrate the following algorithm has O(nlogn) time complexity

1 Answers1