# Need help with algorithm analysis

1) find the kth largest value in an unsorted array of N elements. Estimate the running time. It should be better than quick sort running time. I think O(n + klogn) is an efficient running time (if you can do a better algo, please do so). I don't need the entire program. Just functions that show the timing. This is how I did it. Please correct my solution

kthLargest(A,n) {

BuildMaxHeap(A);

for(I=1; I<=k; I++)

kth[I] = GetMax(A);

} time = O(n + klogn)

BuildMAxHeap(A) {

heapsize[a] = length[A];

for(I= length[A]/2; I>= 1; I--)

MaxHeapify(A,I);

} time = O(n/2 logn)

GetMax(A) {

if(heapsize[A] < 1)

return error

max = A[1]

A[1] = A[heapsize[A]]

heapsize[A] = heapsize[A] - 1

MaxHeapify(A,1)

return max;

} time = O(logn)

3) What is running time of insertion sort if all keys are equal.

4) How to recursively multiply XY, where X = 2222 and Y = 4321

This is from book. I understand what is happening, however, I don't know how to write a recursive function for this! I hope this helps.

Suppose we want to multiply two n-digit numbers x and y. If exactly one of x and y is negative, then the answer is negative; otherwise it is positive. Thuse we can perform this check and then assume that x,y >= 0. If x = 61,438,521 and y = 94,736,407, xy = 5,820,464,730,934,047. Let us break x and y into two halves. Then x1 = 6,143, x2 = 8,521, y1 = 9473, and y2 = 6,407.

We also have x = x1 * 10^4 + x2 and y = y1* 10^4 + y2

xy = x1y1*10^8 + (x1y2 + x2y1)10^4 + x2y2

x1y2 + x2y1 = (x1 - x2)(y2 - y1) + x1y1 + x2y2

Figure below shows how only 3 recursive subproblems need to be solved

Function Value Complexity

x1

x2

y1

y2 6,143

8,521

9,473

6,407 Given

Given

Given

Given

d1 = x1 - x2

d2 = y2 - y1 -2,378

-3,066 O(n)

O(n)

x1y1

x2y2 58,192,639

54,594,047 T(n/2)

T(n/2)

d1d2

d3 = d1d2 + x1y1+ x2y2 7,290,948

120,077,634 T(n/2)

O(n)

x2y2

d3*10^4

x1y1*10^8 54,594,047

1,200,776,340,000

5,819,263,900,000,000 Computed above

O)n)

O(n)

x1y1*10^8 + d3*10^4 + x2y2 5,820,464,730,934,047 O(n)

,

5) Write a function to traverse a general tree stored with child/sibling with postorder.

ADT:

typedef struct node *node_ptr

struct node {

type elem;

node_ptr child;

node_ptr sibling;

}

The tree should be something like below where black arrows are children and reds are siblings.

#### Solution Summary

The solution provides an algorithm analysis for N elements by creating a program to run.