Question

ChangeString (s,x):
   change = ""
   for i from 1 to lenght(s):
       ignore = false
       for k from 1 to length(x):
           if s[i] == x[k]:
               ignore = true
       if ignore == false:
           change += s[i] //assume this line is O(1) time
   return change

isTheSame (s, t, x):
   a = ChangeString (s, x)
   b = ChangeString (t, x)

   if length(a) != length(b):
       return false
   for i from 1 to lenghth(a):
       if a[i] != b[i]:
           return false
   return true

What is the worst case run time of isTheSame? Justify.

Answer 1

As there are two independent nested "for"loop in ChangeString() so it will take n^2 time

isTheSame (s, t, x):
   a = ChangeString (s, x) //It take n^2 time
   b = ChangeString (t, x) // it also take n^2 time

   if length(a) != length(b): //It will take some constant time
       return false
   for i from 1 to lenghth(a): //it will take n time
       if a[i] != b[i]: //it will take constant time
           return false
   return true

Total time will be

(n^2) + (n^2) + c1 + n + c2

=2*(n^2) + n + C

In big O notation will take upper bound so we have

O() time complexity for  isTheSame​​​​​​​()