Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Big O

MongloidooMongloidoo Member Posts: 52
An algorithm that is O(lg n) takes 10 seconds to execute on a particular machine when n=10, how long should it take when n=80?

An algorithm that is O(n) takes 10 seconds to execute on a particular machine when n=100, how long should it take when n=500?

An algorithm that is O(n^2) takes 10 seconds to execute on a particular machine when n=500, how long should it take when n=500?


Jeez, how do i figure out this big o stuff? this stuff is confusing.

Comments

  • IllcoIllco Member Posts: 382
    No it really isn't - it's actually a simplification of the time complexity of an algorithm. The Big-Oh notation specifes an upper bound to the time complexity; so it should not exceed that (worst case). The expression within the brackets is likely to be parametrized; it mostly depends on n. Mostly n is an indication of the amount of input.

    So say for example we're discussing a sorting algorithm. Since there are numerous algorithms with varying applications, they vary in time complexity. You could say one algorithm runs in O(n) time and another one in O(n^2) time. This means that, given n number to sort the first one sorts this in a time linearily proportional to that number. The second one sorts n numbers in time quadratically proportional to that number.

  • Shawn CarterShawn Carter Member Posts: 0

    _____ { http://forcoder.org } free video tutorials and ebooks about | R PHP Assembly C# Go Objective-C Scratch Java Delphi Swift C++ Perl JavaScript C Ruby Python Visual Basic PL/SQL Visual Basic .NET MATLAB Scala Fortran F# ML Apex Prolog FoxPro Scheme Crystal D Logo Erlang Ada Awk SAS Alice Lua Clojure Lisp LabVIEW COBOL Bash VBScript ABAP Hack Julia Dart Rust Transact-SQL Kotlin | ______

Sign In or Register to comment.