Results 1 to 3 of 3

Math Help - Big O for sequential algoritms

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    1

    Arrow Big O for sequential algoritms

    If an algoritm consists of for instance two sequential calculations with a given time complexity as below, what is the total complexity for the algo?

    ALGO:
    calculate_one() // O(n)
    calculate_two() // O(n)

    Time complexity for each is O(n), is it true that the total time complexity is O(n+n) = O(n) in worst case?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by avantimedev View Post
    If an algoritm consists of for instance two sequential calculations with a given time complexity as below, what is the total complexity for the algo?

    ALGO:
    calculate_one() // O(n)
    calculate_two() // O(n)

    Time complexity for each is O(n), is it true that the total time complexity is O(n+n) = O(n) in worst case?
    The complexity is O(n) for whatever case conditions appy to the sub-calculations, if one is worst case then its worst case, if both are average case then its average case etc

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Yes. It follows from the definition of the big O notation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Sequential Limit
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: February 15th 2011, 06:57 PM
  2. Sequential Order of Numbers
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 3rd 2010, 09:39 AM
  3. Sub-sequential limit point
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: June 26th 2010, 08:14 AM
  4. sequential compactness
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: May 11th 2010, 08:56 AM
  5. Sequential Proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 4th 2009, 11:00 AM

Search Tags


/mathhelpforum @mathhelpforum