Recent content by ZERO_COOL

Can anyone else help with this?

Homework Statement Suppose that v is of type Vector of Integers and we know the following:- 1. v is sorted. 2. No two items in v are the same. 3. v.at(1) is 12. For an integer n, where 1 <= n <= v.size(), let p(n) be the following proposition: p(n): v.at(n) => 11 + n. A. Explain why...

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

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

I've used induction to get the formula as T(n) = 5n + 4. Classifying this as O(f(n)) for a suitable function of f in the Big Oh hierarchy I get. f(n) = 5n + 4 = O(n). This is because n is the dominant term. I'm pretty sure on this just need a quick nod of approval if possible. Thanks,

Technically I do not have a formula to prove via induction. I am trying to work out a formula from the recurrence system. My goal is not to prove an established formula for a recurrence system but rather establish a formula for a recurrence system. So when I am able to establish a...

I have guessed at the formula being that it is a fairly simple pattern. I was taught that induction is used to prove a formula is a solution of a recurrence system when you have been given the solution. I'm trying to solve a recurrence system first using this algebraic technique. It's my...

Homework Statement Solve the recurrence system below and dtermine a formula for the time complexity function T(n). T(0) = 4. T(n) = 5 + T(n - 1) (n > 0) The Attempt at a Solution T(3) = 5 + T(2). T(2) = 5 + T(1). T(1) = 5 + T(0). T(3) + T(2) + T(1) = 3 * 5 + T(2) + T(1) + T(0)...

Thanks Mark and phyzmatix. I was about 80% confident in my answers now I'm 100% :)

Yep LOL, I was hoping someone could verify my answers, the brackets have me doubting my answers and I'm a bit dubious about my response to the third one.

Homework Statement Give the order of the following functions, 1. Ta(n) = 20^2 + (n + 4)^3 2. Tb(n) = (6n + 4)^2 + 3nlog2(n) 3. Tc(n) = (7n + 1)^2log10(n) Homework Equations The Attempt at a Solution I got the following orders:- 1. Θ(n^3) 2. Θ(n^2) 3...

Still struggling with this, feel as though I'm banging my head against a brick wall. I'm not sure how to put it all together into a meaningful proof.

What your saying makes sense to me, I understand it. I'm not sure how p(k - 1) comes into play. I fairly sure I'm learning from bad text because the book is based entirely on using mathematical induction as proof for recurrence systems. Yet this question doesn't involve a recurrence system...

I'm still struggling to work this out, so any help appreciated.

Yes it does. Given that v is sorted and no item in the vector is identical then:- v.at(n) > v.at(n - 1). Where does p(k - 1) come into play?