turing machine computes a function in time..

[malleat1]

hi guys

im doing discrete maths right now, we're studying about turing machines... unfortunetely, there is somthing i dont seem to pick up , what does it mean for a turing machine,say N, to compute a function in time O(T(n))?

Thanx in advance
Hannah

[kedaman]

That's the big O notation, which exposes only the most essential characeteristics of the computation time, as a function of the amount of elements n you are operating on.

for instance, if an algorithm takes 5n*log2(6n)+4 time, then T=n*log(n) in O(T(n)), you usually see this notation: O(n*log(n)) when looking at for instance sorting algorithms.

When you do a big O notation, sort out all constants, then sort out all except the most significant term, i.e. the one that grows fastest toward infinity when n increases, for instance n^4 wins against n^3, and 2^n wins against n^4 (x^y symbolising x to the power of y). If you are unsure which grows fastest then you can always test them with big enough numbers, but its better to memorize the order in which the functions grows. Another way is dividing one with the other, and if the function tends toward 0 when n grows, then the denominator wins otherwise the numerator.