Asymptotic Notation

Abstract Data Types:

For user-defined data types we also need to define operations. The implementation for these operations can be done when we want to actually use them. That means, in general, user defined data types are defined along with their operations.

we combine the data structures with their operations and we call this Abstract Data Types (ADTs). An ADT consists of two parts:

1. Declaration of data

2. Declaration of operations

Why Algorithm Analysis?

Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed.

What is Running Time Analysis?

It is the process of determining how processing time increases as the size of the problem (input size) increases.

Types of Analysis

•Worst case

Defines the input for which the algorithm takes a long time (slowest time to complete). ○ Input is the one for which the algorithm runs the slowest.

•Best case

Defines the input for which the algorithm takes the least time (fastest time to complete). ○ Input is the one for which the algorithm runs the fastest.

•Average case

Provides a prediction about the running time of the algorithm.

Run the algorithm many times, using many different inputs that come from some distribution that generates these inputs, compute the total running time (by adding the individual times), and divide by the number of trials.

Assumes that the input is random.

Lower Bound < = Average Time < = Upper Bound

Why log(n) is considered better complexity?
For example: there is a for loop
for(int i=0;i<n;i++) this runs n times thus making the complexity O(n)
but if we have
for(int i=0;i<n;i/2) this runs n/2 times each time thus making the complexity O(log n)














Problem1: Find the complexity of the below recurrence T(n) = 3T(n-1) 
T(n) = 3T(n-1)  
T(n-1) = 3T(n-1), replacing T(n-1)
T(n) = 3(3(t(n-1))
T(n) = 3sqaureT(n-1)
Complexity = 3 power n