Question

Task 1. to be completed.

1.1 - Write a small Python snippet code that can revert an array of N element (Please do not use the default function “reverse()).

1.2 - There is a famous programming (algorithm) concept that can vastly reduce the complexity of Recursive Fibonacci Algorithm. 2 .a) What is the name of this concept 2.b) Write the execution time and memory complexity of Fibonacci sequences, once this concept is applied 2.c) Explain the main idea behind this concept, and how it reduces the execution time complexity.

1.3 - There is a bound over the runtime complexity of sorting algorithms if no assumption is made on the type of input. Write two algorithms that serve as an exception to this bound and explain what their additional assumption on the input is.

1.4 - Write the average running time complexity of Selection, Insertion, Mergesort, Quicksort, and Radix sort algorithms with Big-O notation.

1.5 - Explain why the array must be sorted in order for binary search to work. Your answer must relate the sorting requirement with the complexity of binary search (e.g., provide a counter example that violates complexity etc)

1.6 - What is the Big-O complexity of Binary Search for input size N. Write just one Big-O term.

Answer 1

#The string reverse program in Python is:

a = input("Enter the String which you wnat to reverse: ") #Enter the input which you waat to reverse
b = "" #Create an empty string
for i in a: #using for loop to reverse the string
b = i+b
print ("The reverse of %s is: %s"%(a,b)) #print the string which is reversed

1.2.

2a. The name of the method is "Golden Ration"

2b. The execcution time of the fibonnci series once this method applied is "O(1.6180)^n" . and the memory required is 7772 kilobytes.

2c. The main idea behind this concept is quadratic equations

1.4. The average runtime of  

selection = O(n)

Insertion = O(n)

Merge sort = O(nlog(n))

quick sort = O(nlog(n))

Radix Sort = O(n+b)*log(bk)  whare b is the base of the log and k is the maximum value

1.5 Generally binary search works on the princple of finding the middle of the array which has the value if median in array. if the binary search is not sorted, the assumptions which we are assuming will not work. because the median will be diffrent places and slicing the array into half may mean that you slice the number that we are searching for

1.6 The time complexity of binary search is O(log2(N))

where 2 is base of the log and and N is number of times the operation has to perform.

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

Kindly comment your queries if any, upvote if you like it. Thank you!!