Home Forums SQL Server 7,2000 T-SQL O(n) , O(n log n), O(n^2) RE: O(n) , O(n log n), O(n^2)

  • June 9, 2009 at 4:24 am

    #1006564

    karthikeyan (6/9/2009)

    Big O notation means the steps to complete a problem. Right?

    No. Not at all.

    Big O notation describes the time complexity of an algorithm. That is describes how the time required to solve an algorithm will increase as the number of inputs (n) increases.

    A linear algorithm (O(n)) is one where the time required to solve the algorithm increases linearly with the number of inputs. So if 1000 inputs takes 1 minute to solve, 2000 inputs will take 2 minutes to solve and 5000 inputs will take 5 minutes to solve.

    A quadratic algorithm (O(n2) is one where the time required to solve the algorithm increases quadratically with the number of inputs. So if 1000 inputs takes 1 minute to solve, 2000 inputs will take 4 minutes to solve and 5000 inputs will take 25 minutes to solve. (roughly)

    I'm curious. Where and when did you do your MCA? Where and when did you do your undergrad Comp Sci degree?

    Gail Shaw
    Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
    SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

    We walk in the dark places no others will enter
    We stand on the bridge and no one may pass