# Efficiency Problems

Page 1 of 1

## 1 Replies - 1768 Views - Last Post: 21 March 2007 - 07:32 PM

### #1 lonrot

• New D.I.C Head

Reputation: 0
• Posts: 1
• Joined: 10-February 07

# Efficiency Problems

Posted 10 February 2007 - 03:27 PM

Hi:

I am having serious problem with these problems

1)if T(n) has the property that T(0) is O(1) and T(n) <= T(n-1) + f(n), where f(n) is a function that consumes and returns a natural number which is O(n), then T(n) is O(n^2), but i need to prove this by induction on n, using the definition of O-notation, how can i do it?

For this problem i am guessing that i need to find a relation between You're given a relation between T(n), T(0) and f but i dont seem to find it.

2)This problem is in 2 parts, the first 1 is
a)
```(define (mod-exp1 m e n)
(cond
[(zero? e) 1]
[else (modulo (* (mod-exp1 m (- e 1) n) m) n)]))

```

*The code is in scheme if anyone interested; anyways it's a recursive function where cond is equal to if in other languages and (* a b c) = (a*b*c).

Assuming that m E{0,...,n-1}, let T_1(e) be the number of multiplications needed to compute (mod-exp1 m e n) on any legal input. Give an explicit formula for T_1(e).

For this i think it should take e numbers of multiplication or at least thats is what i deducted so it could be something like this??

T_1(e)= a + (T_1 e -1) where a is a positive constants and are some steps or should it be 1 because it's counting the number of multiplications??

```(define (mod-exp2 m e n)
(cond
[(zero? e) 1]
[(even? e) (modulo (mod-exp2 (sqr m) (quotient e 2) n) n)]
[else (modulo (* (mod-exp2 (sqr m) (quotient e 2) n) m) n)]))

```

where (sqr m) = m^2

Let T_2(e) be the number of multiplications needed to compute (mod-exp2 m e n). Describe T_2(e) by a recurrence relation, indicating what the diffrent cases are. Give an estimate for T_2(e) in O-notation.

Hint:Assume that 2^(L-1) < e <2^L. What is the cost of the algorithm in terms of L? what is the relationship between L and n?

but im still in doubt on this one

Thanks for the help

Is This A Good Question/Topic? 0

## Replies To: Efficiency Problems

### #2 salindor

• D.I.C Regular

Reputation: 46
• Posts: 302
• Joined: 10-November 06

## Re: Efficiency Problems

Posted 21 March 2007 - 07:32 PM

lonrot, on 10 Feb, 2007 - 03:27 PM, said:

Hi:

I am having serious problem with these problems

1)if T(n) has the property that T(0) is O(1) and T(n) <= T(n-1) + f(n), where f(n) is a function that consumes and returns a natural number which is O(n), then T(n) is O(n^2), but i need to prove this by induction on n, using the definition of O-notation, how can i do it?

For this problem i am guessing that i need to find a relation between You're given a relation between T(n), T(0) and f but i dont seem to find it.

2)This problem is in 2 parts, the first 1 is
a)
```(define (mod-exp1 m e n)
(cond
[(zero? e) 1]
[else (modulo (* (mod-exp1 m (- e 1) n) m) n)]))

```

*The code is in scheme if anyone interested; anyways it's a recursive function where cond is equal to if in other languages and (* a b c) = (a*b*c).

Assuming that m E{0,...,n-1}, let T_1(e) be the number of multiplications needed to compute (mod-exp1 m e n) on any legal input. Give an explicit formula for T_1(e).

For this i think it should take e numbers of multiplication or at least thats is what i deducted so it could be something like this??

T_1(e)= a + (T_1 e -1) where a is a positive constants and are some steps or should it be 1 because it's counting the number of multiplications??

```(define (mod-exp2 m e n)
(cond
[(zero? e) 1]
[(even? e) (modulo (mod-exp2 (sqr m) (quotient e 2) n) n)]
[else (modulo (* (mod-exp2 (sqr m) (quotient e 2) n) m) n)]))

```

where (sqr m) = m^2

Let T_2(e) be the number of multiplications needed to compute (mod-exp2 m e n). Describe T_2(e) by a recurrence relation, indicating what the diffrent cases are. Give an estimate for T_2(e) in O-notation.

Hint:Assume that 2^(L-1) < e <2^L. What is the cost of the algorithm in terms of L? what is the relationship between L and n?

but im still in doubt on this one

Thanks for the help

Looking at the date, proably been too long sense you posted, but it looks to me like a recurrance relation.

Salindor