CSE 214 Lecture Notes - Lecture 1: Big O Notation

• School: Stony Brook University
• Department: Computer Science
• Course: CSE 214
• Professor: Ahmad Esmaili

Document Summary

Used to describe the performance or complexity of an algortihm. Big o specifically describes the worst- case scenario and can be used to describe the execution time required or the space used by an algorithm. How to determine big o notation: different steps get added, drop constants, different inputs = different variables, drop non dominate terms. Describes an algorithm that will always execute in the same time regardless of the size of the inout data set. If each statement is "simple" (only involves basic operations) then the time for each statement is constant and the total time is also constant: o(1). 4 bool isfirstelementnull(ilist elements) return elements[0] == null; Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. bool containsvalue(ilist elements, string value) foreach (var element in elements) if (element == value) return true;