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)
CODE
(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??
CODE
(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
| 