CMPT 125 Study Guide - Final Guide: Time Complexity, Sorting Algorithm

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Write a function that gets a binary search tree and prints all items in the tree in an increasing order. Use big-o notation to express the running time of your function. print_sorted (btnode* root) { // print inorder traversal if (root == null) return; print_sorted(root->left); printf( %d , root->data); print_sorted(root->right); Runtime is o(n) since for each node we make o(1) operations. Suppose we have struct called some_data: typedef struct { } some_data; and a comparison function compare_data(some_data* d1, some_data* d2) that returns 1 if d1 > d2, returns -1 if d1 <= d2. A function array_to_bst() that gets an array of n elements of some_data, and creates a bst containing all the elements, where the items are compared using the function compare_data(). Prove that the running time of array_to_bst() must be at least nlog(n) Solution: denote the running time of array_to_bst() by t(n). Claim: we can use it to design a sorting algorithm in time t(n) + o(n).