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

#1 lonrot  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Re: Efficiency Problems

Posted 21 March 2007 - 07:32 PM

View Postlonrot, 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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1