Efficiency Problems

[lonrot]

Hi:

I am having some problems with this problems of efficiency, can someone help me plz :


1)As you know in big O notation, if T(n) has the property that T(0) is O(i) 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?

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; 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).

b)

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?

thanks for the help

[Cervantes]

Hey lonrot, welcome to CompSci.ca

It's interesting that you took your CS136 homework here. Why not the newsgroup, or tutorials?

Anyways, I haven't started the assignment yet, myself, but I'm guessing that T_1 is O(n) and T_2 is O(log n). For T_2, in any case other than the base, we're doing at least one multiplication (it's hidden in the sqr function). In the case where e is odd, we're doing two multiplications. But that two is a constant so it shouldn't matter when we get our final answer in O notation.


So, after I've blathered for a bit, do you have a specific question? Of course it's unfair to answer the question completely. Besides, that's not the best way to learn.

[lonrot]

Bullseye =), anyways i am actually just trying to get an idea of how to solve them, like for example for number 1 i dont know how to start, i can't find a relation between T(n), T(0) and f to start with it.
For the second problem (mod-exp1 m e n) my idea first was to know how many times does it take from when e= 1,2,3.., and so on so i tried with stepper and i found that it should be proportional to e, O(n), but how can i give the explicit formula for T_1(e).

P.D., i dont go to tutorials because they are usually kind of useless , the examples they give us are really easy and have no point on see in them, at least for me, also when i go to the tutors like they dont really want to say anything directly related to the homework at the end they dont say anything so it's usually bad. Normally i go to the teacher but i couldn't this week so...

thanks anyways

[wtd]

I'm tempted to move this to Functional Programming.

[we64]

lol, assignment help here eh? yeah, should just do it in the newsgroup, most of the time is quite clear there if you ask.

Just looked through the assignment, seems very bothersome, but definitly important and definitly will be a big part on the exam. Damn..