c# - Does adding extra loop at the end of n(log n) algorithm affect the complexity? -

i wrote algorithm find length of longest increasing sequence in array.

the algorithm has array m contain sequence in conditions, doesn't contain exact sequence. in such case, record index , value needs changed.

this algorithm n(log n)

now, find actual sequence, loop through array m , replace value recorded in array. algorithm still have complexity if n(log n) ?

below code in c#:

        int[] b = { 1, 8, 5, 3, 7, 2, 9 };          int k = 1;          int = 1;         int n = b.length;           list<int> m = new list<int>();         int[] lup = new int[b.length];          m.add(0);         m.add(b[0]);         lup[0] = 0;         while (i < n)         {             if (b[i] >= m[k])             {                 k = k + 1;                 m.add(b[i]);             }             else             {                 if (b[i] < m[1])                   {                     m[1] = b[i];                 }                 else                 {                     int j;                     j = binary_search(m, b[i], m.count - 1);                     //if item replaced not last element, record                     if (m[j] > b[i] && j != k)                     {                         lup[j] = m[j];                     }                     m[j] = b[i];                  }             }             = + 1;          }          console.writeline("the input sequence : " + string.join("\t", b));         console.writeline("length of longest sequence : " + k.tostring());          list<int> result = new list<int>();          // create result based on m , lup         //does loop effect performance??         for(int x = 1; x < m.count; x++)         {             if (lup[x] == 0)             {                 result.add(m[x]);             }             else             {                 result.add(lup[x]);             }         } 

your intuition correct. adding loop n*(log(n)+1) it's still n*log(n).