Class Notes (807,242)
CSC165H1 (160)
Lecture

# tut07handout.pdf

3 Pages
82 Views

School
University of Toronto St. George
Department
Computer Science
Course
CSC165H1
Professor
Nathalie Fournier
Semester
Fall

Description
CSC165H1F Tutorial # 7 Fall 2011 1. Write a detailed, structured proof that 8f : N ! R ;8g : N ! R ;g 2 O(f) ) g 2 O(f ) 2 (where f and g are de▯ned in the obvious way: 8n 2 N;f (n) = f(n) ▯ f(n), and similarly for g). Dept. of Computer Science, University of Toronto, St. George Campus Page 1 of 3 CSC165H1F Tutorial # 7 Fall 2011 2. Prove that T (n) 2 ▯(n ), where BFT is the algorithm below. BFT BFT(E;n): 1. i n ▯ 1 2. while i > 0: 3. P[i] ▯1 4. Q[i] ▯1 5. i i ▯ 1 6. P[0] n 7. Q[0] 0 8. t 0 9. h 0 10. while h 6 t: 11. i 0 12. while i < n: 13. if E[Q[h]][i] 6= 0 and P[i] < 0: 14. P[i] Q[h] 15.
More Less

Related notes for CSC165H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.