Hi, could you please tell me the big-O notation for this algorithm?
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Hi, could you please tell me the big-O notation for this
![3
|
3
3
3
3
3
def insertion_sort(my_array):
# Traverse through 1 to len (my_array)
num_ops = 3
for i in range (1, len(my_array)):
key=my_array[i]
3
def merge_sort(my_array):
num_ops = 3
if len(my_array) > 1:
mid = len(my_array) // 2 # Finding the mid of the array
L=my_array[:mid] # Dividing the array elements
R = my_array[mid:] # into 2 halves.
g
3
9
j=i-1
num_ops += 9
while j >= 0 and key < my_array[j]:
my_array[j+ 1] = my_array[j]
j -= 1
3
3
num_ops += 9
my_array[j+ 1] = key
num_ops += 3
return num_ops
num_ops += 6 + len(my_array)
if len (L) >= 32 and len(R) >= 32:
op1 = merge_sort (L)
op2 = merge_sort (R)
num_ops += 4
else:
op1 insertion_sort(L)
op2= insertion_sort (R)
num_ops += op1 + op2
i=j= k = 0
Len L = Len (L)
Len R = Len (R)
# Copy data to temp arrays L[] and R[]
num_ops += 11
while i < len_L and j < len_R:
num_ops += 4
if L[i] < R[j]:
my_array[k] = L[i]
i += 1
num_ops += 3
else:
my_array[k] = R[j]
j += 1
num_ops += 3
k += 1
num_ops += 5
# Checking if any element was left
num_ops += 2
while i < len_L:
my_array[k] = L[i]
i += 1
k += 1
num_ops += 6
num_ops += 2
while j < len_R:
my_array[k] = R[j]
j += 1
k += 1
num_ops += 6
return num_ops](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F442cdeaf-d6f5-4c90-9eca-defd0049fe9f%2F0bf4adce-5656-47dd-9feb-490dcba77a0b%2Fxkymyew_processed.png&w=3840&q=75)
Transcribed Image Text:3
|
3
3
3
3
3
def insertion_sort(my_array):
# Traverse through 1 to len (my_array)
num_ops = 3
for i in range (1, len(my_array)):
key=my_array[i]
3
def merge_sort(my_array):
num_ops = 3
if len(my_array) > 1:
mid = len(my_array) // 2 # Finding the mid of the array
L=my_array[:mid] # Dividing the array elements
R = my_array[mid:] # into 2 halves.
g
3
9
j=i-1
num_ops += 9
while j >= 0 and key < my_array[j]:
my_array[j+ 1] = my_array[j]
j -= 1
3
3
num_ops += 9
my_array[j+ 1] = key
num_ops += 3
return num_ops
num_ops += 6 + len(my_array)
if len (L) >= 32 and len(R) >= 32:
op1 = merge_sort (L)
op2 = merge_sort (R)
num_ops += 4
else:
op1 insertion_sort(L)
op2= insertion_sort (R)
num_ops += op1 + op2
i=j= k = 0
Len L = Len (L)
Len R = Len (R)
# Copy data to temp arrays L[] and R[]
num_ops += 11
while i < len_L and j < len_R:
num_ops += 4
if L[i] < R[j]:
my_array[k] = L[i]
i += 1
num_ops += 3
else:
my_array[k] = R[j]
j += 1
num_ops += 3
k += 1
num_ops += 5
# Checking if any element was left
num_ops += 2
while i < len_L:
my_array[k] = L[i]
i += 1
k += 1
num_ops += 6
num_ops += 2
while j < len_R:
my_array[k] = R[j]
j += 1
k += 1
num_ops += 6
return num_ops
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education