CODEWITHSUNDEEP
algorithmrecursion
Tono Nam
Tono Nam

Reputation: 36048

Find recurrence relation equation to the following algorithm

It has been estimated that a specific social network site has the following number of users per month.

F(n)= F(n-1)*120% + 100*n  where F(0)=0

this means that every month 100 new users are added because of advertisement and 20% more users are added per month due to users inviting people the the social network. Also on the first month there are no users.

Anyways if we plug in numbers to this recursion we will get:

F(0)=0
F(1)=F(0)*1.2 + 100*1=100
F(2)=F(1)*1.2 + 100*2=320
F(3)=F(2)*1.2 + 100*3=684
F(4)=F(3)*1.2 + 100*4=1220.8
F(5)=F(4)*1.2 + 100*5=1964.96
....

Anyways I have answer the first part of that question. Now I am stuck in solving that recursive relation. I need to find an equation that will solve the recurrence relation. In other words a function that if I where to pass the number 2 then it will output 320 for example without having to call itself.

The answer is actually: enter image description here

I don't understand how to get to that solution. I got that answer from HERE. I will like to understand how to solve it not just get the solution.

Upvotes: 3

Views: 1269

Answers (4)

user1105089
user1105089

Reputation: 1

f(n)=af(n-1)+bn =a[af(n-2)+b(n-1)+b(n-1)]=a^2f(n-2)+(a+1)b(n-1) -ab

in general f(n) =a^n * x + n*y+z

now f(1)=a*x+y+z=1 f(2)=(a^2)* x+2y+z= f(3)=...

We can sole this linear system to get x,y ,z

Upvotes: 0

Saeed Amiri
Saeed Amiri

Reputation: 22555

Mathematical View

instead of 1.2 I'll use a and instead of 100 I'll use b (a>1,b!=0):

F(n) = aF(n-1) + bn ==>
F(n) = a (aF(n-2) + bn) + bn 
     = a^2 F(n-2) + ab(n-1)+bn 
     = a^3F(n-2) + a^2 * b * (n-2)+a*b*(n-1)+b*n=...
     = a^n F(0) + a^(n-1) * b * (n-(n-1)) + .... + bn
     = 0 + a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b -
           [a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ... + 0)

if we write:

A = a^(n-1)* nb + a^(n-2)* (n-1)b + ... + a^0 *1*b
B = a^(n-1)* (n-1)b + a^(n-2) * (n-2)b + ...

You need to find A-B.

then

A = b (a^n + a^n-1 + a^n-2 + ....)'
B = b/a * (a^(n-1)+....)' - a

and if we let C = a^n + a^n-1 + a^n-2 + .... we know C = (a^(n+1) - a)/(a - 1) and simply you can calculate C' and finally you can calculate A and B and their difference A - B.

Algorithmic and real working view

But if I want to talk in context of algorithms, I'm care about O and Θ and Ω , ... not about exact running time.

So when I see your algorithm I say It's Θ(an) without any calculation, because if you replace bn with 1, it doesn't affect your Θ notation because your function grows exponentially so removing some constant or polynomial functions (without converting them to zero) doesn't change exponential running time, and It just removes some polynomial function from final result. So in this cases I never try solid maths. I'll use solid math in writing academic papers or exams not in real life.

Upvotes: 2

maxim1000
maxim1000

Reputation: 6365

F(n)=A*F(n-1)+B*n

What we have here looks like an exponent with linear addition.

The idea is to find C and D which make true the following equation:

F(n)+C*n+D=A*(F(n-1)+C*(n-1)+D)

then we can introduce another function: G(n)=F(n)+C*n+D

G(n)=A*G(n-1)

G(n)=E*A^n (E can be found from starting condition)

F(n)=A^n-C*n-D

Now let's actually find C and D:

B*n=A*C*(n-1)+A*D-C*n-D=(A*C-C)*n+A*D-D-A*C

B=C*(A-1) - this will give us C

0=A*D-D-A*C - this will give us D (provided C is already known)

Upvotes: 0

Tono Nam
Tono Nam

Reputation: 36048

I wish I had come up with the solution that I posted earlier. This is what I have worked out and I guess that since I got an equation (non recursive) that can be a correct solution.

enter image description here

Upvotes: -1

Related Questions