CSC 110 Lecture Notes - Lecture 31: Quicksort, Big O Notation, Selection Sort
5 May 2016
School
Department
Course
Professor
Document Summary
Go through an array to find a certain target value. Locates target value in a sorted array listed( which is from lowest to highest value, Searching for middle number will effectively cut search in half. A measure of the use of computing resources by code. Any single java statement takes the same amount of time to run. Method call"s runtime is measured by total of statements inside the method"s body. Measure runtime in proportion to input data size, (n) Growth rate: change in runtime as n changes. Ex: if algorithm runs at 0. 4^3 + 25n^2 +8n +7 than the degree of the highest order will most affect runtime. We ignore constants like 17 because they are tiny, and so n^3 dominates overall runtime. We say that algorithm runs on the order of n^3 or o(n^3) Rearranging values in an array or collection into a specific order. Ex: take first number and compare if the first is smaller, if not switch.
