CSC263H5 Lecture Notes - Lecture 1: Linked List, Random Variable, Big O Notation
20 Jan 2018
School
Department
Course
Professor
Document Summary
Csc209h5s - software programming and tools (winter 2018) Adt is fixed and you can have various data structures implemented. Example: stack is an adt (stores list of numbers, supports push(), pop(), is_empty()) Data structures that can be used to implement stack (ie. linked list) Amount of resource required by an algorithm, measured as a function of the input size. Number of steps executed by the program/algorithm. : running time of algorithm a with input x. When a is understood, we simply write t(x) The worst-case running time t(n) is defined as: is an input size n} (n) max{t(x) The running time is distributed between the best and worst. Average-case running time is the expectation of the running time which is distributed between 1 and n+1. tn. = random variable for the running time on inputs of length n. n+1. [t ] t=1 t p n = t r(t.
