a puzzle about definition of the time complexity

Viewed 141

Wikipedia defines time complexity as

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

What's mean of the strong part?

I know algorithm may be treated as a function but why its input must be "the length of the string representing"?

3 Answers

The defition is derived from the context of Turing machines where you define different states. Every function which you can compute with a computer is also computeable with turing machine.(i would say that computer computes a function on the basis of turing machine)

Every fucntion is just a mapping from one domain to other domain or same domain.

Before going to Turing machines look at the concept of finite-automata.It has finite states.If your input is of length n then it's possible that it only needs two stats but it has to visit those states n times where n is legnth of the string.

Not a good sketch but look at the image below ,our final state is C , means if
end with a string in c our string will be accepted.

We use unary numberal system. We want to check if this this string gets accepted by our automata: string is 010101010

When we read 0 from A we move to B and if we read again a 0 we will move to C and if we end with 0 our string gets accepted otherwise we move to A again.

In computer you represent numbers as strings with length n and in order to compute it you have to visit each character of the string.

Turing machines work on the same way but finite-automata only is limited to regular languages. How this is a big theory

enter image description here

Did you ever try to think how computer computes a function 2*x where x is your input. It's fun :D . Suppose i want to compute 20*2 and i represent this number with unary numeral system because it's easy. so we represetn 0 with , 1 with 11 , 2 with 111 and etc so if we convert 20 to unary sytem we get 1111. You can think of a turing machine or computer(not advanced) , a system with linear memory.

Suppose empty spots in your memory are presented with # .

With you input you have something like this: ###1111#### where # means empty slot in memory, with your input head of your turing machine is at first 1 so you keep moving forward until you find first # once you find this you just replace it with * which is just a helping symbol and change the right side of # with 1 now move back and change one more 1 to * and write one 1 on the right side when you find a # keep doing this and you will be left with all * on the left hand side and all 1s on the right side, Now change all *s back to 1 and you have 2*x. Here is the trace and you have 2*x where x was your input.

The point is that the only thing these machines remember is the state.

#####1111#######

#####111*1######

#####11**11#####

#####1***111####

#####****1111###

#####11111111###

The function in the bolder part means the time complexity of the algorithm, not the algorithm itself. An algorithm may be implemented in a programming language that has a function keyword, but that's something else.

Algorithm MergeSort has as input a list of 32m bits (assuming m 32-bit values). It's time complexity T(n) is a function of n = 32m, the input size, and in the worst case is bound from above by O(n log n). MergeSort could be implemented as a function in C or JavaScript.

Summary

If there is some input, it is expressed as a string. So you have a length of that string. Then you have a function F that maps the length of the input (as a string) to the time needed by A to compute this input (in the worst case).

We call this F time complexity.


Say we have an algorithm A. What is its time complexity?

The very easy case

If A has constant complexity, the input doesn't matter. The input could be a single value, or a list, or a map from strings to lists of lists. The algorithm will run for the same amount of time. 3 seconds or 1000 ticks or a million years or whatever. Constant time values not depending on the input.

Not much complexity at all to be honest.

Adding complexity

Now let's say for example A is an algorithm for sorting list of integer numbers. It's clear that the time needed by A now depends on the length of the list. A list of length 0 is literally sorted in no time (but checking the length of the list) but this changes if the length of the input list grows.

You could say there exists a function F that maps the list length to the seconds needed by A to sort a list of that length. But wait! What if the list is already sorted? So for simplicity let's always assume a worst case scenario: F maps list length to the maximum of seconds needed by A to sort a list of that length.

You could measure in seconds, CPU cycles, ticks, or whatever. It doesn't depend on the units.

Generalizing a bit

What with all the other algorithms? How to measure time complexity for an algorithm that cooks me a nice meal?

If you cannot define any input parameter then we're back in the easy case: constant time. If there is some input it is expressed as a string. So you have a length of that string. And - similar to what has been said above - then you have a function F that maps the length of the input (as a string) to the time needed by A to compute this input (in the worst case).

We call this F time complexity.

That's too simple

Yeah, I know. There is the average case and the best case, there is the big O notation and asymptotic complexity. But for explaining the bold part in the original question this is sufficient, I think.

Related