Question

Searching/sorting tasks and efficiency analysis - Big-oh

For each problem given below, do the following:
1. Create an algorithm in pseudocode to solve the problem.
2. Identify the factors that would influence the running time of your algorithm. For example, if your algorithm is to search an array the factor that influences the running 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 of the factors you identified in Step 2. To do that, identify the basic operations of the algorithm. There is no need count every statement separately only the ones that will influence the running time.
4. Describe the best case scenario for the algorithm and derive the big O.
5. Describe the worst case scenario for the algorithm and derive the big O.

The problems are:
a. Determine if two arrays have no elements in common.
b. Counting the total number of characters that have a duplicate within a string. (i.e. ”gigi the gato” would result in 7 (g x 3 + i x 2 + t x 2)
c. Finding a row where every entry is ’x’ in a 2-D array.

Answer 1

a. Determine if two arrays have no elements in common

1. Solution Pseudo Code:

INITIALIZE commonElementFound = False

FOR index1 FROM 0 -> length(Array1):

FOR index2 FROM 0-> length(Array2):

IF Array1[index1] == Array2[index2] :

commonElementFound = True

BREAK

ENDIF

ENDFOR

ENDFOR

IF commonElementFound == True:
PRINT " Two Arrays have common elements "

ELSE :
PRINT " Two Arrays have no elements in common"

2. Factors that would influence the running time of algorithm are length of two arrays, naming the factors as "m" and "n"

3. Each step of Pseudocode takes exactly one operation except for loop, where outer for loop is taking m times inner foor loop operations, and inner for loop takes n operations, so loops are taking m*n operations totally

4. The algorithm totally takes m*n operations

5. Best case scenario of the algorithm is when the first element of two arrays are same. So Best case has complexity of big O(1)

6. Worst case scenario is no elements are common in each of the array or last element of array 1 is mathced with last element of array 2 giving the complexity big O(m*n)

----------------------------------------------------------

b. Counting the total number of characters that have a duplicate within a string.

1. Solution Pseudo Code:
INITIALIZE duplicateCharacters = 0
FUNCTION countOccurences( char, String ):
INITIALIZE count = 0
FOR index FROM 0 -> length(String):
IF String[index] == char:
count++
RETURN count
FOR i FROM 0 -> length(String):
count = countOccurences(String[i], String)
IF (count >1):
duplicateCharacters += count
ENDFOR
IF duplicateCharacters == 0:
PRINT " The string doesn't have any duplicate "
ELSE :
PRINT " Total number of characters that have a duplicate within a string are:", duplicateCharacters
2. Factor that would influence the running time of algorithm is length of the string, naming the factor as "n"
3. Each step of Pseudocode takes exactly one operation and for function, it will take as many steps as length of the string.
4. The algorithm totally takes n*n operations.
5. and 6. The best and worst cases are same since the loops are not breaking based on any condition the total time taken by the algorithm is best and worst case so big O(n2) is the complexity

---------------------------------------------------

c. Finding a row where every element is ' x ' in a 2-D array.

1.solution pseudo code :

INITIALIZE foundRow = False ,count = 0,

ROWS = length(array)

COLUMNS = length(array[0])

FOR row FROM 0 -> ROWS:

FOR column FROM 0->COLUMNS :

notMatched = False

IF x != array[row][column] :

notMatched = True

foundRow = True

break

ENDIF

ENDFOR

IF notMatched = False:

print " Row where every element is 'x' is", row

commonRow = True

ENDIF

ENDFOR

IF foundRow == False:

print " No such row exists"

2. Factors that would influence the running time of algorithm are rows and column sizes of matrix. Naming them m for rows and n for columns

3. Each step of Pseudocode takes exactly one unit operation except for loop, where outer for loop is taking m times inner foor loop operations, and inner for loop takes n operations, so loops are taking m*n operations totally

4. The algorithm totally takes m*n operations

5. Best case scenario of the algorithm is when the first element of each row is not ‘x’. and loop just breaks by checking that row. So Best case has complexity of big O(m)

6. Worst case scenario is no elements is ‘x’ in each of the row or last element of each row is not ‘x’ but all starting ones are ‘x’s, giving the complexity big O(m*n)