Question

S19-A6.pdf 2/5 Rutgers University CS111 - Inlroduction to Computer Science Spring 2019 Problem 5 Big-oh For cach problen given below, do lhe following 1. Creste a algrithm in psudood to solve the proble 2. Identify the factors that would influence the running time of your algorithm. For exarple, if your alorithm ia to search an array th fator that influeuxs the runnin time is the array size. Assign names (such as n) to each factor. 3. Count the operations performed by the algorithm. Express the count as a function ol the factors you identified in Step 2. To do that, identify the basic operations of the algorithm. There is noout every statarately only the unes that will inlluence the runing imc. 4. Describe the best case scenario fur the . Ц4urithm and drive the big O . Describe the worst cse scenario for the algorithm and derive the big O The prohlems ae: a. Determine if two array have no elements in como b. Counting the total numher of charscters that have a duplicate within a string, including paces i.e. "gigi the gato" wouldru in 7 (x 3 ix 2 +tx 2 + 'x 2) c. Finding row where every entry is 'x in a 2-D array. Submission

Answer 1

a.

bool common(A1, m, A2, n)

1. For i= 1 to m:-

2.......For j=1 to n

3.............If A[i] == A[j]

4....................Return True //since they have common element

5. Return False //No element found in common

Time complexity = O(mn) in all the cases in total number of comparisons will be m*n. We can reduce this time complexity by sorting array A1 and A2 which takes time O(n log n +m log m) and then comparison for finding duplicate entry will take O(n+m).

b.

int count_duplicate(string s, int n)

1. count= 0

2. Bool checked[256]=false //this will be true if i^th character in ASCII has been checked

3. For i = 1 to n-1

4........... if (s[i] ==true) then continue //since this character has already been checked for duplicate

5............For j= i+1 to n

6..................If(s[i] == s[j] and checked[ s[i] ]== false)

7...........................checked[ s[i] ]= true and count= count+2

8..................Else if(s[i]==s[j] and checked[ s[i] ]==true)

9.......................... count++; //increment count for all duplicate

10 return count //desired result

Here best case will occur if entire string will have same element , in which case time complexity will be O(n) because innerloop will executes only during first iteration of outermost for loop.

Worst case will occur when entire string have different characters where time complexity will be O(n²).

c.

int find_row(A[][], int m, int n, x)

1. For i= 1 to m

2........For j=1 to n

3............. if (A[i][j] !=x)

4...................then continue //since row i do not have all x

5.............. if (j==n) //this means entire row i contain x

6..................then return(i)//since row i has all x

7. Return 0 //if no row have all x

Best case will occur when first entry of every row have value different from x, then time complexity will be O(n)

Worst case will be occur when in each row, every entry is x except the last entry. Then time complexity will be O(n²).

Please comment for any clarification.