[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 30 KB, 355x342, stackoverflow.jpg [View same] [iqdb] [saucenao] [google]
5653766 No.5653766[DELETED]  [Reply] [Original]

Recurrence relations...

I'm supposed to "solve" a recurrence relation where "solve" means to come up with a reasonable upper bound for the time complexity of the relation. So basically I need to express it in big O notation like O(n) where n <= c*n.

I will admit this is a homework question but it's really the conceptual breakthrough I need to understand how I'm supposed to go from an identified pattern of a recurrence relation to a time complexity...

For example, the first relation is T(n) = aT(n-1) + bn.

Expanding it three times brings me to T(n) = a^4T(n-4) + ab(n-3) + ab(n-2) + ab(n-1) + bn

The pattern would be T(n) = a^kT(n-k) + ab(n-(k-1)) + ab(n-(k-2)) + ... + bn.

Assuming a and b are constants and T(1) = 1, what would the time complexity be?

I have difficulty going from the pattern to the time complexity. How do you even do it? Am I supposed to just guess and hope it's the right answer? There has to be a better way.

>> No.5653777

bump 1

>> No.5653816

bump 2

>> No.5653825

Use master theorem. Look it up on wikipedia. Should have learned that in class.

>> No.5653835

>>5653825

Master theorem doesn't work on those recurrence relations. If it was T(n/2) then it would work, but it is T(n-1). Master theorem works on recurrence relations that involve divisions on n.

>> No.5653837

>>5653825
>>5653835

Also the instructions say that I need to come up with an upper bound "given reasonable assumptions about the constants". I am not sure if simply saying b = 0 which would wipe out the entire pattern and leave me with a^k would be reasonable...

>> No.5653843

Sorry, didn't look close enough. The sum you're writing out is O(a^n), though

>> No.5653851

>>5653843

How did you get to that answer? Do I just assume b = 0 and wipe out everything in the pattern except for the first part where we could get a^n from?

>> No.5653860

>>5653851
O(a^k+ba^k-1)=O(a^k) by definition...

>> No.5653875

>>5653860
not if k is negative

>> No.5653883

>>5653860

I am missing something. How did you get to a^k+ba^k-1 or is that an example?

>> No.5653911

Install gentoo.

>> No.5654768

>>5653883

Still missing something as to now he got O(a^n).