COMP 352 Study Guide - Final Guide: Adjacency Matrix, Avl Tree, Binary Search Tree

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Insert the numbers one by one into an originally empty avl tree o(nlogn) => therefore, you can use an avl tree to sort an input list. => generally in a binary search tree would yield inefficient results because it does not have to be a balanced tree. Usually, when you run the algorithm you don"t know whether the input is sorted or not - then time complexity will still be o(logn) In the case of insertion sort, you just compare and swapping is not needed then the time complexity o(n) - this is the best case. Worst case of compare and swap is o(n2) Add pointer to the start index, and move to next index and compare and swap until the element is in the proper place. Start from index 0, search through the entire input to find the minimum & keep track of minimum. Then you swap the minimum with the initial index.