ECS122A-PS1

Question 1: Induction

Find the closed form of:
Prove closed-form formula via induction

Question 2: Analysis

i <-- n;
while (i > 1) { // O(log2(n))
	j = i;
	while (j < n) { // O(log2(n))
		k <-- 0;
		while (k < n) {  // O(n)
			k = k + 2;
		}
		j <-- j * 2;
	}
	i <-- i / 2;
}

Question 3: Analysis

float useless(A) {
	n = A.length; 
	if (n==1) { 
		return A[0];
	}
	let A1, A2 be arrays of size n/2;
	for (i=0; i <=(n/2)-1; i++) {
		A1[i] = A[i]
		A2[i] = A[n/2+i]
	}
	for (i=0; i<=(n/2) -1; i++) { // O(n)
		for (j=i+1; j<=(n/2)-1; j++) { // O(n)
			if (A1[i] == A2[j])
				A2[j] = 0 ;
		}
	}
	b1 = useless(A1); // T(n/2) 
	b2 = useless(A2); // T(n/2)
	return max(b1,b2);
}

Question 4: MinHeap Review

a)

This would be the resulting heap after you push(2), push(31), pop(), pop(),
and update the key of 7 to -2

Transclude of ECS122A-PS1-2024-10-07-12.10.09.excalidraw

b)

It is linear time because of the fact that not all nodes have to undergo the full log(n) operation. The majority of the nodes will end up being inserted in a shallow way, and as the size of the heap approaches infinity, the asymptotic runtime will scale with n, instead of nlogn.

Question 5: Analysis

a)

O(n)

b)

O(n^2)

c)

O(n^3)

d)

O(n^2)

e)

O(n^5)

f)

O(n^3)

Question 6:

is not , however is . This is because grows more rapidly than so there is no c and such that can bound it. On the other hand, since grows more rapidly it can serve as an upper bound for , making it . We could easily find and to prove the O relation for the latter, like and , although other values exist as well.

Question 7:

a)

I will prove that each function is dominated by the function that follows. Since I will be using the limit lemma, I will drop everything but the most dominant term, since other terms will not matter as it approaches infinity:

\displaylines{
n^2 + 3n \geq n^2 \
3n \geq 0
}