Bad performance of the unsorted list (nearly quadratic time) I've already made an implementation of unsorted List but I'm not happy with results it gives. It looks like Big-O is nearly \$N^2\$ which is, I suppose, not correct for my list.

Here's the graph that shows the problem:



The X axis represents number of total operations: adding new elements and same number of deleting max element, Y axis represents time in milliseconds.

If you could show me some lines that could be made better, that would be great. Unfortunately, implementation must contain array types instead of easier and faster List types.

TList.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace list
{
    class TList
    {
        // elements of list
        int[] elements;
        int size;
        public TList()
        {
            size = 1;
            elements = new int[size];
        }
        public void Push(int data)
        {
            size++;
            if(size &gt; elements.Length)
            {
                int[] new_elements = new int[elements.Length * 2];
                elements.CopyTo(new_elements, 0);
                elements = new_elements;
            }
            elements[size - 1] = data;
        }
        public int MaxIndex()
        {
            var index = 0;
            var max = elements[0];
            for(var i=1;i&lt; size;i++)
            {
                if(elements[i]&gt;max)
                {
                    max = elements[i];
                    index = i;
                }
            }
            return index;
        }
        public int[] DeleteAt(int indexToRemove)
        {
            return elements = elements.Where((source, indexOfElements) =&gt; indexOfElements != indexToRemove).ToArray();
        }

    }
}


Another (better?) way to delete:

public void DeleteAt(int indexToRemove)
{
    int[] new_elements = new int[elements.Length - 1];
    for (int i = 0, j = 0; i &lt; size - 1; i++, j++)
    {
        if (i == indexToRemove)
            j++;
        new_elements[i] = elements[j];
    }
    elements = new_elements;
    size--;
}
For now I'm asking how to optimise deleting of MaxIndex from unsorted list


MaxIndex looks fine. Hard to optimize that further. Maybe you can write a normal for loop that goes from zero to less than the array length so that the JIT can optimize away the range check. You then need to insert if (i &gt;= size) break;. The .NET JIT is not good at optimizing so you have to help. RyuJIT, though, does range checks in loops much, much better.

Your delete is highly inefficient. First of all LINQ is the slowest way to create a new array. Better would be to new it manually and then use Array.Copy to copy over the relevant two sections.

Doing it in-place would be again much faster, at least 2x.

The DeleteAt is probably worse than Array.Copy. It is not very good. It does a lot per item and it does not use memcpy like Array.Copy does. Also, there is no need to create a new array. Just copy in place and do size--.