Time Complexity (Big-O)
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:
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?
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.
Life is a short warm moment -
Death is the long cold rest.
By tianming.hu in forum Java
Last Post: 05-18-2006, 05:50 AM
By hfmoller in forum VB Classic
Last Post: 09-05-2005, 05:46 AM
Last Post: 08-08-2005, 11:18 AM
By Terrell in forum Database
Last Post: 10-19-2001, 01:57 PM
By sebasttien in forum Database
Last Post: 02-14-2001, 05:55 AM
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL