Give a big-oh for t(n) the worst-case running time

Assignment Help Computer Engineering

Reference no: EM133240005

Case: Consider the following algorithm pseudocode:

Algorithm Mistery(A[0..n-1,0..n-1]) Input: an n x n array A of integer numbers Output: a boolean value 1. for (i=0; i< n-1; i++) 2. for (j=i+1; j < n; j++) 3. if (A[i,j] != A[j,i]) 4. return false; 5. return true;

Note: when giving the big-Oh , give the tightest upper bound possible. For example, if you can prove that f(n) is O(n) and that f(n) is O(n2), choose the tighter upper bound, ie f(n) is O(n).

Question 1: Give a big-Oh for T(n) the worst-case running time of this algorithm for an input matrix of size n x n. Explain how you obtained this worst case.

Question 2: Give a big-Oh for B(n) the best-case running time of this algorithm for an input matrix of size n x n. Explain the type of inputs (sample inputs) that will give this best case

Reference no: EM133240005

Questions Cloud

What makes it a distinct career or major : ENGL 1301 University of Houston what makes it a distinct career or major, and what outcomes may someone who enters that career or major reasonably expect?

Determine the minimum acceptable price for the job : X Corp. has considerable excess manufacturing capacity. A special job order's cost sheet includes the following manufacturing overhead cost: fixed cost of P 30,

Identify key factors in cultural change within organization : Identify key factors in cultural change within your organization. What tools for change do you believe can be utilized to create change within your organization

How much will be her account after 10 years : In order to buy a new car, Taylor Swift plans to save half of her annual salary of 100,000 at the end of each year for the next 10 years which pays

Give a big-oh for t(n) the worst-case running time : Give a big-Oh for T(n) the worst-case running time of this algorithm for an input matrix of size n x n. Explain how you obtained this worst case

Investment in bob corporation : Prepare a schedule to show the balance Jay should report as its Investment in Bob Corporation at December 31, 2018.

What is the cost of new common stock : Linda Corp paid dividends to Ordinary Shares last year by 2.20 per share. The current market price of Ordinary Shares is 40 per share and investors expect that

Watch the video-classical ballet or contemporary ballet : A short excerpt or variation is sufficient. Please don't forget to label each video: Classical Ballet or Contemporary Ballet.

Book value is attributable to goodwill with indefinite life : Any excess cost over book value is attributable to goodwill with indefinite life. Prepare schedule to show the amount of goodwill from Hay's investment in Joy.

User Account

All Pages