Classifying T(n) as O(f(n)): O(n)

[ZERO_COOL]

Homework Statement

Give a classification of T(n) as O(f(n)) for a suitable function f in the hierarchy of Big Oh.

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

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.

 

[Mark44]

Homework Statement

Give a classification of T(n) as O(f(n)) for a suitable function f in the hierarchy of Big Oh.

Homework Equations

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

You're missing something - what is T(1)? Without this I can't verify your non-recursive formula.

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

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.

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.

 

[ZERO_COOL]

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

Thanks,