How to solve recurrence relation?

[Johnathan Dole]

Hello All, I'm having a little difficulties understanding Recurrence
Relation. We where given a number of Java recursive methods and where asked
to give a recurrence relation that expresses the number of multiplications
performed by the algorithm, and use the recurrence relation to derive a
worst-case time complexity for the algorithm.

public static int power2(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
int part = power2(base, exponent/2);
if (exponent % 2 == 0)
return part * part;
return base * part * part;
}

Would be grealty appriciated if someone could help me solve the followinf
method, so i can try to do the others myself.

Thanks

John

 

[John]

Hello All, I'm having a little difficulties understanding Recurrence
Relation. We where given a number of Java recursive methods and where asked
to give a recurrence relation that expresses the number of multiplications
performed by the algorithm, and use the recurrence relation to derive a
worst-case time complexity for the algorithm.

public static int power2(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
int part = power2(base, exponent/2);
if (exponent % 2 == 0)
return part * part;
return base * part * part;
}

Would be grealty appriciated if someone could help me solve the followinf
method, so i can try to do the others myself.

Thanks

John

Which textbook are you using?

I learnt this stuff using Brassard and Bratley, "Fundamentals of
Algorithmics", Prentice-Hall, 1996.

What you need to do initially is define some f(base, exponent) that
gives the number of multiplications (or elementary operations). This can
be defined recursively. From this you can often obtain a non-recursive
version of f (I can't remember the details but they are in Brassard and
Bratley).

John

 

[Julian V. Noble]

Hello All, I'm having a little difficulties understanding Recurrence
Relation. We where given a number of Java recursive methods and where asked
to give a recurrence relation that expresses the number of multiplications
performed by the algorithm, and use the recurrence relation to derive a
worst-case time complexity for the algorithm.

public static int power2(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
int part = power2(base, exponent/2);
if (exponent % 2 == 0)
return part * part;
return base * part * part;
}

Would be grealty appriciated if someone could help me solve the followinf
method, so i can try to do the others myself.

Thanks

John

I strongly suggest you consult "Alorithms" by Sedgewick, or maybe Knuth's
book "The Art of Computer Programming". Or you could have a look at

http://Galileo.phys.Virginia.EDU/classes/551.jvn.fall01/551Notes.htm

--specifically the chapter "Representation of Functions" where I solve some
recurrences. I also solve some in discussing Strassen's method in the chapter
"Linear Equations".

Deeper insights into difference equations can be gained from

Author: Goldberg, Samuel.
Title: Introduction to difference equations, with
illustrative examples from economics, psychology, and
sociology.

Publication info: New York, Wiley [1958]
Description: 260 p. 24 cm.


--
Julian V. Noble
Professor Emeritus of Physics
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the toothache
patiently." -- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.

 

[Roedy Green]

public static int power2(int base, int exponent) {
if (exponent == 0)
return 1;
if (exponent == 1)
return base;
int part = power2(base, exponent/2);
if (exponent % 2 == 0)
return part * part;
return base * part * part;
}

The basic idea of most recursive programming is you handle the simple
cases, and you simplify any complex case a tad and feed it back into
the same process. As long as you do a little simplification at each
stage, eventually the process will unwind when it hits one of the
trivial cases.

In your example, the simplification is cutting the exponent in half
each go round. This eventually gets to 1. There are many copies of
part -- one for each incarnation of power2.


Try tracing a simple case, see http://mindprod.com/jgloss/trace.html
or just doing it on paper.