FIT1045 Lecture Notes - Lecture 11: Big O Notation, Binary Tree
30 May 2018
School
Department
Course
Professor
WEEK 11 - COMPLEXITY
Complexity
Factors that affect Running Time:
If list is small, running time will be short, vice versa
Present at the start list, small running time,
The less powerful machine, running time will be longer
Analyse algorithm by time complexity when there are factors you cannot
control
RAM:
‘Simple’ operation will take one time unit
Read, print and return will take one time unit
Comparing 2 values one time unit
Several statements will be the sum of statements
Big O notation:
Why do we use it?
Order = find the dominant of the function
Highest growth rate
We ignore the constant numbers (eg. 100 N^2, Big O = O(N^2)
If used on small inputs, the growth rate of the running time may be less
important than other factors
Height = max level in the graph
Balanced Binary Tree
Height of left subtree - height of right subtree is greater or equal to 1
Unbalanced Binary Tree
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
If list is small, running time will be short, vice versa. Present at the start list, small running time, The less powerful machine, running time will be longer. Analyse algorithm by time complexity when there are factors you cannot control. Read, print and return will take one time unit. Several statements will be the sum of statements. Order = find the dominant of the function. We ignore the constant numbers (eg. 100 n^2, big o = o(n^2) If used on small inputs, the growth rate of the running time may be less important than other factors. Height of left subtree - height of right subtree is greater or equal to 1.
