Question 1:
For the given example,
If number is 123, then no of expression will be
12+3, 1+23, 1+2+3
So total number of expressions equal to length of string.
For expression evaluation time take is X unit of time, x might be 10 to the power -9
Then total time taken for evaluate all expression will be n times X= n * X
And X is constant unit of time then algorithm complexity will be O(N)
Question 2:
Recursive multiplication will O(n) unit of time.
Generally this program will have a unit of time equal to smaller of two arguments.
For example if a and b are two arguments.
If a is less than b, then total time take equal to a - 1 or in term of n, n-1 times
If b is less than a, then total time take equal to b - 1 or in term of n, n-1 times
Question 3:
To prove selection short correctness need to prove loop invariant is true
ALGORITHM: sort array of integers
Input: A[1..n] , Array of n unsorted integers
Output: same integers in array A now in sorted order
pseudo code:
for i = 1 to n-1
min = i
for j = i+1 to n
if A[j] < A[min]
min = j
swap A[i] with A[min]
First we prove the correctness of the inner loop: lines 3 to 5
Loop Invariant:
Before the start of each loop, A[min] is less than or equal to A[i..j-1].
First integration of loop, j=i+1. So the array segment A[i..j-1] is really just spot A[i]. Since line 2 of the code sets min = i, we have that
min indexes the smallest element (the only element) in subarray A[i..j-1] and
hence the loop invariant is true.
Comments