Determine the input size and running time for each and justify your answer No co

Question

Determine the input size and running time for each and justify your answer

No coding, ONLY NEED THE INPUT SIZE, RUNNING TIme AND PROVE IT

USING n OR log(n) TO answer the question

don't assume integer is 2 bytes and string is 24 bytes

//determines average of given 4 integers

1. average(int n1, int n2, int n3, int n4)//determines a and returns average of given 4 integers

2. match(String s, String t) //prints all the strings t that appears in given string s as substring

3. gcd(int n, int m) //determines the gratest common divisor of integer m and integer

4. merge(int a[], int b[]) ////merging two sorted array

5. Sort(int a[])   //sort integer array a

6. shortestPath(graph G, int n, int m)   //finds the shortest path from vertex n to vertex m

7. multiplication( matrix A, Matrix B) //multiplays n x k matrix A with k x m matrix B

Explanation / Answer

1. average(int n1, int n2, int n3, int n4)//determines a and returns average of given 4 integers
Takes O(1) , because it takes single operation to find average so its O(1)

2. match(String s, String t) //prints all the strings t that appears in given string s as substring
Let the length of s be n and Let the length of t be m
Takes(nm) time to find all strings that appear in given string s

3. gcd(int n, int m) //determines the gratest common divisor of integer m and integer

Euclidean GCD can make log(MN)

4. merge(int a[], int b[]) ////merging two sorted array
Let the length of a be n and Let the length of b be m
Takesn O(max{n, m})

5. Sort(int a[])   //sort integer array a
Sorting by comparison sort takes at minimum O(logn)

6. shortestPath(graph G, int n, int m)   //finds the shortest path from vertex n to vertex m
Takes at max O(n+m) , We do the BFS

7. multiplication( matrix A, Matrix B) //multiplays n x k matrix A with k x m matrix B
Takesn O(n3) if n is the size of both matrix

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.