time complexity

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 be a function over the natural numbers, to prove the time complexity of P to be equal to we have to show that:

there exists an algorithm that solves P whose time complexity is
the time complexity of every algorithm that solves P is atleast , i.e. the complexity is bound from below by

take the merge algorithm of merge sort as an example, the time complexity of this algorithm is

proving the upper bound: we already know that there exists a solution to merge whose time complexity is

proving the lower bound: we have to show that there exists no merge algorithm whose time complexity is less than

because every merge algorithm would have to construct the output vector whose size is its time complexity cannot be lower than

consider the sum problem, i.e. a function that sums the numbers in its input vector, its time complexity is

proving the lower bound: we already know that there exist sum functions that run in time

proving the upper bound: we have to show that there exists no sum algorithm whose time complexity is less than

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

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

at first glance this might seem like a algorithm but its time complexity is actually

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 , which means the algorithm is bound by