Time Complexity (Big-O)

[icu222much]

Aloha

If this thread is posted in the wrong place, please move it

Earlier I came across a topic called Time Complexity and it dealt with the Big-O notation. I don't quite understand this and I was wondering if anyone would care to explain it to me ?

I understand that Time Complexity deals with the amount of time it takes to complete processing a function. What I don't understand is how you come up with the following formulas:

O(n)
O(n2)
O(n2log2 n)

Thank you
-Jon

[gregorw]

Based on Limit theory and Complexity theory - in Mathematics as functions approach Infinity they approach Non-Deterministic Polynomial Time (NP Complete) in computer lingo, in laymen terms, they are Unsolvable. The Big-O notation is used to describe the efficiency of an algorithms' worst case example. The "basic" Big-O functions of 'n' you posted above are examples of stuff that is computed in Polynomial Time. Meaning, it is solvable, but how long will it take? A millisecond, a minute, a day, a lifetime?

[drkybelk]

Hi,
the notation give you the "housenumber" of the complexity of a problem. For Example
multiplying two square (n x n) matrices you will need n*n*n multiplications and about the same number of additions. In computing terms the multiplications are far more costly than additions so for estimating the complexity they are not taken into account. Hence the complexity is O(n3). Before somebody shouts out loud: Yes, there is a better algorithm than the naive one with a complexity of O(n2log2 n).
For any practically interesting number n (say 100) a reduction of O(n3) to O(n2log2 n)
makes a *HUGE* difference in computation time. There are many problems (Travelling Salesman etc.) which are easily programmable, but for any interesting number of n simply take too long to compute O(NP), so suboptimal approximations are devised.

Cheers,

D