Time Complexity (Big-O)


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Time Complexity (Big-O)

  1. #1
    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. #2
    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. #3
    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
    DKyb
    -------------------------------
    Life is a short warm moment -
    Death is the long cold rest.
    Pink Floyd
    -------------------------------

Similar Threads

  1. Need help and GMT0 time transform local time?
    By tianming.hu in forum Java
    Replies: 0
    Last Post: 05-18-2006, 05:50 AM
  2. Measure Time Remaining Of A Process
    By hfmoller in forum VB Classic
    Replies: 2
    Last Post: 09-05-2005, 05:46 AM
  3. Make applet taking the server time?
    By mmvsbg in forum Java
    Replies: 1
    Last Post: 08-08-2005, 11:18 AM
  4. Big Time SQL Problem
    By Terrell in forum Database
    Replies: 0
    Last Post: 10-19-2001, 01:57 PM
  5. Replies: 0
    Last Post: 02-14-2001, 05:55 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center