CSUS Help desk is hosting a
JAVA BOOTCAMP
Thursday September 17th from 5:30pm to 7h30pm
This bootcamp is aimed to programmers who don’t know the particularities of Java. There will be an overview of syntactic and semantic difference between java and other coding languages, with a focus on OOP (including polymorphism and inheritance).
The zoom link is: https://mcgill.zoom.us/j/92101531362
COMP251: Running time analysis and the Big O notation
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides from M. Langer and M. Blanchette
Outline
• The Big O notation o Definition
o Examples o Rules
• Big Omega and Big Theta • Applications
• Motivations
Measuring the running “time” • Goal: Analyze an algorithm written in
pseudocode and describe its running time
– Without having to write code
– In a way that is independent of the computer used
• To achieve that, we need to
– Make simplifying assumptions about the running time of each basic (primitive) operations
– Study how the number of primitive operations depends on the size of the problem solved
Primitive Operations
Simple computer operation that can be performed in time that is always the same, independent of the size of the bigger problem solved (we say: constant time)
– Assigning a value to a variable: x ¬1
– Calling a method: Expos.addWin()
– Note: doesn’t include the time to execute the method
– Returning from a method: return x;
– Arithmetic operations on primitive types
x + y, r*3.1416, x/y, etc.
– Comparisons on primitive types: x==y
– Conditionals: if (…) then.. else…
– Indexing into an array: A[i]
– Following object reference: Expos.losses
Tassign Tcall
Treturn Tarith
Tcomp Tcond Tindex Tref
Note: Multiplying two Large Integers is not a primitive operation, because the running time depends on the size of the numbers multiplied.
FindMin analysis
Algorithm findMin(A, start, stop)
Input: Array A, index start & stop
Output: Index of the smallest element of A[start:stop]
minvalue ¬ A[start] minindex ¬ start
index ¬ start + 1
while ( index <= stop ) do {
if (A[index]