Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Big Oh notation

  1. May 16, 2010 #1
    1. The problem statement, all variables and given/known data
    Give a classification of T(n) as O(f(n)) for a suitable function f in the hierarchy of Big Oh.

    2. Relevant equations
    T(n) = 5 + T(n - 1) (n > 0) *THIS IS PART OF THE RECURRENCE SYSTEM.

    T(n) = 5 + 5N. *THIS IS THE FORMULA FOR THE TIME COMPLEXITY FUNCTION. WORKED OUT BY SOLVING THE RECURRENCE SYSTEM.

    3. The attempt at a solution
    I've got confused, not sure if I give a classification of the formula that I worked out by solving the recurrence system or of the recurrence system.

    I think it is the formula T(n) = 5 + 5n. In which case I *think* it's a no brainer because the only term is 5n and so,

    T(n) = 5n is (O^2) and also it is O(n). Thus T(n) = 5n is of order n. Which means 5n is BIG THETA O(n).

    Would appreciate ir if someone could verify I'm on the right track with this.
     
  2. jcsd
  3. May 16, 2010 #2

    Mark44

    Staff: Mentor

    You're missing something - what is T(1)? Without this I can't verify your non-recursive formula.
    If T(n) = 5 + 5n, then T(n) is O(n). I have no idea what O^2 means or what BIG THETA O(n) means. It's been a long while since I worked with this stuff, and I don't remember learning about BIG THETA or O^2. Otherwise, I agree that T(n) = O(n), assuming your nonrecursive formula is correct.
     
  4. May 17, 2010 #3
    The recurrence system part I didn't include was T(0) = 4.

    Thanks,
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook