Time Complexity
posted by Anonymous
posted 2y 97d ago
Number of operations is defined as:
\\ F(0) = 1 \\ F(1) = 1 \\ F(n) = 2F(n-1)+F(n-2)+3

Then it follows that

\\ F(n-1) = 2F(n-2)+F(n-3)+3\\ F(n-2) = 2F(n-3)+F(n-4)+3\\ \vdots\\ F(n-k) = 2F(n-(k-1))+F(n-(k-2))+3

Note that

\\ F(n) = 2F(n-1)+F(n-2)+3 \\ = 2(2F(n-2)+F(n-3)+3) + F(n-2)+3 \\ = 5F(n-2) + 2F(n-3) + 9 \\

Calculating a few more terms gives us the big picture:

Let P(n) be the n-th term in the sequence of Pell numbers (0,1,2,5,12,...). Then, for k > 1,

F(n) = P(k+2)F(n-k)+P(k+1)F(n-(k+1))+3\cdot (3\cdot 2^{k-1}-4)


Now let n-k = 1 thus k = n-1. Calculating F(n) gives us

F(n) = P(n+1)F(1) + P(n)F(0)+ 3\cdot (3\cdot 2^{n-2}-4)


Using the definition of our recursive function F, we get

P(n+1)+P(n)+3\cdot (3\cdot 2^{n-2}-4)


Ignoring the numbers, we can conclude the sequence has exponential growth rate.

Reply to this post

Replies

Time Complexity
posted by Anonymous
posted 346d 8h ago
Number of operations is defined as:
\\ F(0) = 1 \\ F(1) = 1 \\ F(n) = 2F(n-1)+F(n-2)+3

Then it follows that

\\ F(n-1) = 2F(n-2)+F(n-3)+3\\ F(n-2) = 2F(n-3)+F(n-4)+3\\ \vdots\\ F(n-k) = 2F(n-(k-1))+F(n-(k-2))+3

Note that

\\ F(n) = 2F(n-1)+F(n-2)+3 \\ = 2(2F(n-2)+F(n-3)+3) + F(n-2)+3 \\ = 5F(n-2) + 2F(n-3) + 9 \\

Calculating a few more terms gives us the big picture:

Let P(n) be the n-th term in the sequence of Pell numbers (0,1,2,5,12,...). Then, for k > 1,

F(n) = P(k+2)F(n-k)+P(k+1)F(n-(k+1))+3\cdot (3\cdot 2^{k-1}-4)


Now let n-k = 1 thus k = n-1. Calculating F(n) gives us

F(n) = P(n+1)F(1) + P(n)F(0)+ 3\cdot (3\cdot 2^{n-2}-4)


Using the definition of our recursive function F, we get

P(n+1)+P(n)+3\cdot (3\cdot 2^{n-2}-4)


Ignoring the numbers, we can conclude the sequence has exponential growth rate.

Use this to start your reply
Time Complexity
posted by Anonymous
posted 336d 12h ago
Number of operations is defined as:
\\ F(0) = 1 \\ F(1) = 1 \\ F(n) = 2F(n-1)+F(n-2)+3

Then it follows that

\\ F(n-1) = 2F(n-2)+F(n-3)+3\\ F(n-2) = 2F(n-3)+F(n-4)+3\\ \vdots\\ F(n-k) = 2F(n-(k-1))+F(n-(k-2))+3

Note that

\\ F(n) = 2F(n-1)+F(n-2)+3 \\ = 2(2F(n-2)+F(n-3)+3) + F(n-2)+3 \\ = 5F(n-2) + 2F(n-3) + 9 \\

Calculating a few more terms gives us the big picture:

Let P(n) be the n-th term in the sequence of Pell numbers (0,1,2,5,12,...). Then, for k > 1,

F(n) = P(k+2)F(n-k)+P(k+1)F(n-(k+1))+3\cdot (3\cdot 2^{k-1}-4)


Now let n-k = 1 thus k = n-1. Calculating F(n) gives us

F(n) = P(n+1)F(1) + P(n)F(0)+ 3\cdot (3\cdot 2^{n-2}-4)


Using the definition of our recursive function F, we get

P(n+1)+P(n)+3\cdot (3\cdot 2^{n-2}-4)


Ignoring the numbers, we can conclude the sequence has exponential growth rate.

Use this to start your reply
Submit Reply
Title: Your Name:
Wrap equations in [EQ]equation here[/EQ] tags, and inline equations in [IEQ][/IEQ] tags.