I had a session today with my colleagues to practise the defense for an important scholarship. One of the work packages in my project is the determination of the lower bound complexity of a specific new algorithm. The colleagues questioned whether I would be able to define bounds on the complexity of the problem before finding an algorithm that actually solves the problem.

Now I'm sure this must be possible because, if one takes sorting as an example for instance, it doesn't take long to realise that one needs to iterate over at least every element to sort a whole array (hence linear complexity as the absolute lower bound). In practise ofcourse average sorting complexity will be n log n. It seems like a conclusion one could arrive at before knowing even one sorting algorithm.

Is it possible to determine complexity bounds of a problem before discovering an actual algorithm? If so, did this happen before (like with sorting e.g.), so I could use that particular case to motivate my answer?

Thanks very much,

Jeroen

**Edited by godmodder, 19 October 2012 - 09:13 AM.**