# Big Oh notation

1. May 16, 2010

### ZERO_COOL

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. May 16, 2010

### 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.

3. May 17, 2010

### ZERO_COOL

The recurrence system part I didn't include was T(0) = 4.

Thanks,