We are given a code symmetry, that takes an n x n matrix as its argument. It returns true if the matrix is symmetric and false if it is not. The run time of the code is calculated by counting how many times the /= comparison is executed. procedure symmetry(M) for x:=1 to (n-1) for y:=(i+1) to n if mxy /= myx then return false else return true (a) Calculate the best case run time for symmetry (will be a number). (b) Calculate the worst case run time for symmetry (will be a polynomial in n, it will be helpful to draw matrices of different sizes and compare the number of comparisons to find a pattern). (c) Determine the worst case run time in big O notation

We are given a code symmetry, that takes an n x n matrix as its argument. It returns true if the matrix is symmetric and false if it is not. The run time of the code is calculated by counting how many times the /= comparison is executed. procedure symmetry(M) for x:=1 to (n-1) for y:=(i+1) to n if mxy /= myx then return false else return true (a) Calculate the best case run time for symmetry (will be a number). (b) Calculate the worst case run time for symmetry (will be a polynomial in n, it will be helpful to draw matrices of different sizes and compare the number of comparisons to find a pattern). (c) Determine the worst case run time in big O notation

Related questions

Q: Given an n×n matrix A and n×1 right-hand side b, write a function that carries out q iterations of…

A: Given an n×n matrix A and n×1 right-hand side b, write a function that carries out q iterations of…

Q: ALGORITHM 1 A Procedure for Computing the Transitive Closure. procedure transitive closure (MR:…

A: Python has a simple and easy-to-learn syntax, making it a popular choice for beginners. It…

Q: Given an array arr] and an integer K wh K is smaller than size of array, the task find the Kth…

A: The problem statement is to find the Kth smallest element in an array. You are given an array arr[]…

Q: Compute the code that return the matrix M = AT A for a given matrix A - the superscript T denoted…

A: import numpy as np def multiply_At_A(A): dim1 = A.shape[0] dim2 = A.shape[1] matrix =…

Q: explain l

A: The question is asking to determine the time complexity of a given function that uses both iteration…

Q: Use this algorithm to code this pseudocode in Python.

A: Python has a simple and easy-to-learn syntax, making it a popular choice for beginners. It…

Q: Write the code using vpasolve and find the x and y values. (1) ((log(x)/log(3))+3y=13, x^2-2y=1

A: We need to solve the given equations using vpasolve. ***As per the guidelines only 1st question is…

Q: Consider the following algorithm: function MYSTERY(A, n) /Input: Array A and integer n. A has size…

A: If T(n) is time complexity for MYSTERY(A,n) . Now on each function call we perform O(1) . And on…

Q: 2: - Write a recursive function that takes an array and a callback function and returns True if any…

A: Note: This is a python code to check whether the number is even or not. The function takes an array…

Q: Why are arrays so useful?

A: Arrays are a fundamental data structure old in computer indoctrination. They are a collection of…

Q: , Is there are other functional dependencies? If so, what are they? If not, why not? Do you believe…

A: The question asks to identify functional dependencies in a dataset of pet records and consider…

Q: Please follow the following code format and not coping other codes cuz it doesn't work THANK YOU! IN…

A: Solution def gaussq(A, b, q): n = len(A) Aa = [[0] * (n+1) for i in range(n)] for i in range(n): for…

Concept explainers

Problems on amortized analysis

Amortized analysis is a technique used to perform micro-level analysis of an algorithm's complexity or resource (time and memory) consumption. It is used for analyzing the time efficiency of data structures that support many operations such as stacks and heaps.Operations supported by stack include push, pop, multi push, and multi pop while operations supported by heap are inserted, delete, extract-min, and so forth. It focuses on the sequence in which these operations are executed and therefore, provides an accurate cost estimation.

Question

procedure symmetry(M)

for x:=1 to (n-1)

for y:=(i+1) to n

if m_xy /= m_yx then return false

else return true

(a) Calculate the best case run time for symmetry (will be a number).

(b) Calculate the worst case run time for symmetry (will be a polynomial in n, it will be helpful to draw matrices of different sizes and compare the number of comparisons to find a pattern).

(d) Using the following definition of big O notation, prove the answer to (c)

Definition: Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f(x) is O(g(x)) if there are constants C and k such that whenever x > k. [This is read as “f(x) is big-oh of g(x).”]

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1: Define as big O and worst-case scenario

VIEW

Step 2: Define as big O and worst-case scenario for all parts

VIEW

Solution

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, data-structures-and-algorithms and related others by exploring similar questions and additional content below.

Similar questions

Complete the following Code
When you have a matrix below, how do you print this as a matrix? Example) mat = 1 2 3 2 3 4 When you do the following for-loop, what do you get? Cumulative addition of each element in either row or column direction.
Write in Python
The goal of this problem is to walk from cell (0, 0) to cell (m, n) of a two-dimensional array. Each step must be either to the right or downward. So you can step from cell (1, 1) to cell (1, 2) or (2, 1). but not from (1, 1) to (0, 1) or (1,0). You are given a toll matrix, where each cell contains a toll that must be paid upon entry into that cell. The goal is to make it from cell (0, 0) to cell (m, n) while paying the smallest possible total toll. Does a greedy algorithm work? Think it out. Write a dynamic programming algorithm that finds the minimum possible total toll. It does not need to do reconstruction and say how to achieve that total toll.
Compute the code that return the matrix M = A" A for a given matrix A - the superscrupt T denoted the transpose. I have started the code for you, which gets the dimension of the matrix, and creates the zero matrix of the correct size. I have also provided some of the loops involved. In [ ]: # perform and return the multiplication of $A^TA$ import numpy as np def multiply_At_A(A): # these lines set up the correct dimensions of the returned matrix. # the matrix A is of dimension diml x dim2 # the matrix A^T (transpose of A) is dim2 x diml # the matrix (A^T A) is of dimension dim2 x dim2 diml = A.shape[0] A.shape[1] = np.zeros ([dim2,dim2]) dim2 matrix for i in range(dim2) : for j in range(dim2) : # complete the final loop to compute matrix[i,j] # your code here return matrix
python # Initialize a 6x6 matrix with all elements as 0 matrix = [[0 for _ in range(6)] for _ in range(6)] # Fill in the matrix for i in range(6): # Iterate over rows for j in range(6): # Iterate over columns if i > j: matrix[i][j] = 3*j - 4*i else: matrix[i][j] = 0 # Print the matrix for row in matrix: print(row)
B. Write a program to print the elements of secondary diagonal of matrix: 区- 1
If you run this piece of code, you will get an error. Why? a = [0 1 2 3; 4 5 6 7]; a = a^2; matlb does not allow you square all the elements in matrix in a single operation you must use the * operator instead of the operator A you are attempting to multiply a non-square matrix by itself, causing O a dimension mismatch you cannot square matrices that have 0 as the first element O
DESIGN YOUR OWN SETTING Devise your own setting for storing and searching the data in an array of non-negative integers redundantly. You may just describe the setting without having to give an explicit algorithm to explain the process by which data is stored. You should explain how hardware failures can be detected in your method. Once you have described the setting, make sure to include the following: Write a pseudocode function to describe an algorithm where the stored data can be searched for a value key: if the data is found, its location in the original array should be returned; -1 should be returned if the data is not found; -2 should be returned if there is a data storage error Include a short commentary explaining why your pseudocode works Describe the worst-case and best-case inputs to your search algorithm Derive the worst-case and best-case running times for the search algorithm Derive the Theta notation for the worst-case and best-case running times Maximum word count for…
In python, how do you generate a distance matrix H where in each entry hij, the distance between row i and row j are stored, distance is computed by the inner product <x,y>C := xTCy, where the matrix C is a 3x3 matrix: [3 1 6 1 2 1 6 1 27]. The dataset is a 26x5 matrix and I need to find the distance using the above inner product between each row - I should end up with a 26x26 distance matrix H, where each diagonal entry (i=j) is 0.
Define, A = Find x. Hint: use numpy.linalg.inv and the @operator for matrix multiplication. 3 6 2 b = 10 5 2 1 7 5 Y = 3 Ax + b = Y N