HOMEWORK 8: QUAD TREES AND TREE ITERATION NAME: < insert name > COLLABORATORS AND OTHER RESOURCES: List the names of everyone you talked to about this assignment (classmates, TAs, ALAC tutors, upperclassmen, students/instructor via LMS, etc.), and all of the resources (books, online reference material, etc.) you consulted in completing this assignment. < insert collaborators / resources > Remember: Your implementation for this assignment must be done on your own, as described in "Academic Integrity for Homework" handout. ESTIMATE OF # OF HOURS SPENT ON THIS ASSIGNMENT: < insert # hours > ORDER NOTATION ANALYSIS: Give the big O notation of each of the QuadTree operations and justify your answer for the non trivial operations (please be concise!) Analyze both the running time and the additional memory usage needed (beyond the space allocated for the existing tree structure). You may assume that the tree is reasonably well balanced for all operations. n = the number of elements in the tree size() running time: memory usage: insert() running time: memory usage: find() running time: memory usage: height() running time: memory usage: begin() running time: memory usage: end() running time: memory usage: bf_begin() running time: memory usage: bf_end() running time: memory usage: operator++() running time: memory usage: operator*() running time: memory usage: getLabel() running time: memory usage: getDepth() running time: memory usage: copy constructor running time: memory usage: assignment operator running time: memory usage: destructor running time: memory usage: EXTRA CREDIT: TREE BALANCING How does the point insertion order affect the shape of the resulting QuadTree object? What are specific examples of the worst case and best case? Discuss your stratgy for reordering the input to rebalance the tree. Paste example output with and without your rebalancing. MISC. COMMENTS TO GRADER: (optional, please be concise!)