This week we covered time efficiency and asymptotic notations. There are three main types of notations when it comes to time efficiency (or time complexity): Big-O, Big-Theta, and Big-Omega, with Big-Omega being less commonly used. Big-O notation considers the upper bound -- Meaning all functions with lower or same order of growth as f(n). Big-Theta is more precise -- All functions with the same order of growth as f(n). While, Big-Omega is the lower bound -- meaning all functions with same or higher order of growth as f(n). To figure out the order of growth, you must consider the number of executions of the basic operation of the algorithm. To represent the order of growth in Big-O notation, you must find the dominant factor and eliminate coefficients. For example, if the number of executions can be represented by 0.5n³ + 500n², the dominant order is n³ and we eliminate the coefficient, so the order is O(n³). Big-Theta is used to represent the average time, but cannot be used if the best and worst case efficiencies are different.
The most difficult part of this week for me was considering the mathematical part of analysis. Using backward substitution and establishing base conditions and recurrence relations is definitely something I need to review.
No comments:
Post a Comment