Question

In: Computer Science

def anagramSolution1(s1,s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and...

def anagramSolution1(s1,s2):
alist = list(s2)

pos1 = 0
stillOK = True

while pos1 < len(s1) and stillOK:
pos2 = 0
found = False
while pos2 < len(alist) and not found:
if s1[pos1] == alist[pos2]:
found = True
else:
pos2 = pos2 + 1

if found:
alist[pos2] = None
else:
stillOK = False

pos1 = pos1 + 1

return stillOK

include all operations and calculate the Big-O and the values for c and n0.

Solutions

Expert Solution

For the better understanfing of the complexity I will explain the complexity of each line one by one.

  1. This operation is just an assignment operation which will take constant time means O(1)
  2. similar to line this will also take O(1) time
  3. Now let's consider the length of s1 is n, now because this loop is running n times the operation which are taking place inside this loop of O(1) time complexity will take O(n) time after n run.
  4. Now let's consider the length of alist is m, since this is also a loop running m number of times inside a loop which is running n number of times time complexity for this loop will be O(m*n) time.
  5. All the other statements inside this loop are either if or else are taking O(1) time. So overall complexity of this program will be O(m*n) time.

The order of times complexity of any algorithm is always the statement which is taking largest amount of time, because our focus is always on the worst case scenario.

We know that f(n)= O(g(n)) iff f(n)<=c*g(n) where c is a positive constant with c>=1

So time coopmlexity T(n) of the given code is

T(n)=O(m*n)., where m and n are length of strings list and s1 respectively. Value of c=1 and n0=1


Related Solutions

If there are two energy states, S1 and S2 respectively such that S2>S1 then there exists...
If there are two energy states, S1 and S2 respectively such that S2>S1 then there exists some probability for an atom in S2 to decay to S1. What actually causes the atom to decay to the lower energy state? is it the fact that the lower state is more probable for the atom to be in as given by the Boltzmann Factor? so since it is more probable, it has more microstates and entropy causes it to decay? Please help...
def longest(string): start=0;end=1;i=0; while i<len(string): j=i+1 while j<len(string) and string[j]>string[j-1]: j+=1 if end-start<j-i: #update if current...
def longest(string): start=0;end=1;i=0; while i<len(string): j=i+1 while j<len(string) and string[j]>string[j-1]: j+=1 if end-start<j-i: #update if current string has greater length than #max start and end end=j start=i i=j; avg=0 for i in string[start:end]: avg+=int(i) print('The longest string in ascending order is',string[start:end]) print('Teh average is',avg/(end-start)) s=input('Enter a string') longest(s) i need a definition and explanation of this code that how it works?
def myLength(mylist):    count = 0    for index in range(len(myList)):        print(myList[index])       ...
def myLength(mylist):    count = 0    for index in range(len(myList)):        print(myList[index])        count = count + 1    return count def myLength2(mylist):    count = 0    for element in myList:        print(element)        count = count + 1    return count       Use these two functions as examples to write your Python function below! Function 1: Write a function called myCount that takes in two parameters (a list and an item) like...
The functions are tested in the following main(): def recSum1(somelist): if len(somelist) == 1: return somelist[0]...
The functions are tested in the following main(): def recSum1(somelist): if len(somelist) == 1: return somelist[0] else: a = recSum1(somelist[:len(somelist)//2]) b = recSum1(somelist[len(somelist)//2:]) return a + b def recSum2(somelist): if len(somelist) == 1: return somelist[0] else: return somelist[0] + recSum2(somelist[1:]) import random def main(): N = 100 myList = [random.randint(-500, 500) for i in range(N)] print(myList) print("The sum of the numbers is: " + str(sum(myList))) print("The sum of the numbers using recSum1 is: " + str(recSum1(myList))) print("The sum of the...
Program in C: The strncpy(s1,s2,n) function copies exactly n characters from s2 to s1, truncating s2...
Program in C: The strncpy(s1,s2,n) function copies exactly n characters from s2 to s1, truncating s2 or padding it with extra null characters as necessary. The target string may not be null-terminated if the length of s2 is n or more. The function returns s1. Write your own version of this function. Test the function in a complete program that uses a loop to provide input values for feeding to the function.
True or False) The following code will output "I was true". bool isGreater(string s1, string s2)...
True or False) The following code will output "I was true". bool isGreater(string s1, string s2) { if(s1 > s2) { return true; } return false; } int main() { if(isGreater("before","back")) { cout << "I was true"; } else { cout << "I was false"; } return 0; }
Suppose you have two strains of mice, S1 and S2. Strain S2 is genetically modified to...
Suppose you have two strains of mice, S1 and S2. Strain S2 is genetically modified to metabolize a pharmacon P supposedly faster than S1. You conducted an experiment in a sample set of each strain, in which the pharmacon was injected and its concentration in blood was measured every 15min for 2h. Of course, age, gender, and weight was recorded for each animal. You want to statistically demonstrate that the metabolic rate of N is higher in S2 than S1....
if s1 and s2 are two simple functions then prove that the max and minimum of...
if s1 and s2 are two simple functions then prove that the max and minimum of then are also simple function.
The intersection (∩) of two sets (s1, s2) is the set of all elements that are...
The intersection (∩) of two sets (s1, s2) is the set of all elements that are in s1 and are also in s2. Write a function (intersect) that takes two lists as input (you can assume they have no duplicate elements), and returns the intersection of those two sets (as a list) without using the in operator or any built-in functions, except for range() and len(). Write some code to test your function, as well. Note: Do not use the...
Let S = (s1, s2, . . . , sn) be a given sequence of integer...
Let S = (s1, s2, . . . , sn) be a given sequence of integer numbers. The numbers can be positive or negative. We define a slice of S as a sub- sequence (si,si+1,...,sj) where 1 ≤ i < j ≤ n. The weight of a slice is defined as the sum of its elements. Provide efficient algorithms to answer each of the following questions: a)Is there any slice with zero weight ? b)Find the maximum weight slice in...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT