Algorithm and Data structure: Algorithm Analysis

Introduction

•The role of algorithm analysis is to estimate resource consumption
•Algorithm analysis methods:
–Empirical analysis
–Mathematical (theoretical) analysis


Algorithm Analysis

•Algorithm analysis
–Is the process of estimating the running time of an algorithm
–The main consideration in algorithm analysis is the size of input
•Algorithm Efficiency
–In order to determine the efficiency of an algorithm, we have to consider how the running time of an algorithm grows with the amount of data
–Algorithm that grows slower is considered to be more efficient than those that grow faster
–The best method for this estimation is to use the O notation


Estimating Running Time

•Multiple Consecutive Line
•Looping
•Nested Loops
•If-Else
•For Loop

Case Analysis

•Best Case, Average Case and Worst Case Analysis


Selecting Best Algorithm

•Points to concern when writing a program is:
–Nested looping will reduce algorithm efficiency, in fact, deep nested loops is very bad for program efficiency
–Recursive can be more efficient than looping but be careful not to wrongly implement recursion. It can produce horrible result
–The structure of the data is also important. If the data is structured wrongly, it may have more tendencies to run in worst case
•Selecting the best algorithm depends on your program requirement:
–Critical parts of your program may require more efficient algorithm because the tendency of the parts to be executed is more often
–Parts that are seldom use may need less efficient but simple to code algorithm