DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Aug 2006
Posts
1

Time Complexity (Big-O)

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

2. Registered User
Join Date
Aug 2006
Posts
3
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?

3. Registered User
Join Date
Jan 2005
Location
UK
Posts
604
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

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise