time complexity of algorithms

let P be a computational problem, the complexity of P is the time complexity of the fastest possible algorithm that solves P

the time complexity of an algorithm is defined as the amount of time taken by it to run, as a function of the length of the input

let P be a computational problem, let $\text{[math]}$ be a function over the natural numbers, to prove the time complexity of P to be equal to $\text{[math]}$ we have to show that:

there exists an algorithm that solves P whose time complexity is $\text{[math]}$
the time complexity of every algorithm that solves P is atleast $\text{[math]}$ , i.e. the complexity is bound from below by $\text{[math]}$

take the merge algorithm of merge sort as an example, the time complexity of this algorithm is $\text{[math]}$
_proving the upper bound_:
we already know that there exists a solution to merge whose time complexity is $\text{[math]}$
_proving the lower bound_:
we have to show that there exists no merge algorithm whose time complexity is less than $\text{[math]}$
because every merge algorithm would have to construct the output vector whose size is $\text{[math]}$ its time complexity cannot be lower than $\text{[math]}$

consider the sum problem, i.e. a function that sums the numbers in its input vector, its time complexity is $\text{[math]}$
_proving the lower bound_:
we already know that there exist sum functions that run in $\text{[math]}$ time
_proving the upper bound_:
we have to show that there exists no sum algorithm whose time complexity is less than $\text{[math]}$
because every sum algorithm would have to check each item in its input vector atleast ones, we know it has to perform atleast n operations, which means that its time complexity cannot be lower than $\text{[math]}$

best case

best case is the time complexity of the case with the least work done, i.e. the case in which the time complexity is minimal

average case

the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

worst case

worst case is the time complexity of the case with the most work done, i.e. the case in which the time complexity is maximal

best conceivable runtime

the best conceivable runtime means it is the best time you can conceive that the problem could possibly be solved in, and it is definitely impossible for the problem to be solved faster than that

examples

$\text{[math]}$ at first glance this might seem like a $\text{[math]}$ algorithm but its time complexity is actually $\text{[math]}$
we track the variable lastp, every time we enter the third inner loop it is decremented and is never incremented until it reaches a point at which the while loop wouldnt execute anymore, this can happen N times at most
each time the first main loop run, the second and third inner loop both may in total run N times at most because they are both bound by lastp and j which get closer to each other every time either loop runs
and so the time complexity of the two inner loops is bound by $\text{[math]}$ , which means the algorithm is bound by $\text{[math]}$