In this blog, we will be solving some problems related to data structure and algorithm analysis. Below are the questions
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)
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
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
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
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.
Contact Codersarts for any such project/assignment help
Codersarts is a top-rated website for students which is looking for online Programming Assignment Help, Homework Help, Coursework Help in C, C++, Java, Python, Database, Data structure, Algorithms, Final year project, Android, Web, C sharp, ASP NET to students at all levels whether it is school, college and university level Coursework Help or Real-time project. Hire us and Get your projects done by a computer science expert.