Mathematical Analysis of Non recursive Algorithms

Examples of O(1) algorithms are______________.

• A. Multiplying two numbers.

• B. assigning some value to a variable

• C. displaying some integer on console

• D. All of the above

Examples of O(n2) algorithms are______________.

• A. Adding of two Matrices

• B. Initializing all elements of matrix by zero

• C. Both A and B

• D. Neither A nor B

The complexity of three algorithms is given as: O(n), O(n2) and O(n3). Which should execute slowest for large value of n?

• A. O(n)

• B. O(n2)

• C. O(n3)

• D. All will execute in same time.

Express the formula (n-1)*(n-5) in terms of big Oh notation

• O(1)

• O(log n)

• O(n)

• O(n2)

EXAMPLE 1 Consider the problem of finding the value of the largest element in a list of n numbers. For simplicity, we assume that the list is implemented as an array. The following is pseudocode of a standard algorithm for solving the problem.

ALGORITHM MaxElement(A[0..n − 1])

//Determines the value of the largest element in a given array

//Input: An array A[0..n − 1] of real numbers

//Output: The value of the largest element in A maxval ← A[0]

for i ← 1 to n − 1 do

if A[i] > maxval maxval ← A[i]

return maxval

Is the algorithm correct for the above question?

• yes

• no