1. State the size of the input in big-Oh. For example, if the input to an algorithm is an array of size k, then the input size is O(k).

2. Derive the cost function for the algorithm. You can use O(1) to denote all constants.

3. State the complexity of the algorithm in Big-Oh. The complexity MUST be stated in terms of input-size.

see example

Example: Multiplication Solution 1. The inpput size is O(k)+O(k)O(k) 2. f(k)=O(1)+kO(1)+k2O(1) 3. f(k)O(k2) input: integer n output: closest integer that is the square root of n 1=1h=n while 1