University:
Massachusetts Institute of Technology
Course:
16.01 | Unified Engineering I, II, III, & IV
Academic year:

2021
Views:

153

Pages:

2
Author:

trescandogss

Lecture C9 Response to 'Muddiest Part of the Lecture Cards' (10 respondents) 1) What is T(n)? We are trying to get an equation of the time taken to solve a problem of size n. We represent the total time taken as T(n). We will see more of this in detail in the next lecture. 2) For T(n) = Csn/2, the bound was n/2 ≤ n, and we said that this was valid for n≥ 1, so n0 = 1. But isn’t n/2 ≤ n valid for all n ≥ 0? Yes mathematically that is correct, but n=0 is an empty array, and the worst case, best case and average case are all constant time. 3) Why do we use Big-O? Big-O notation allows us to perform an asymptotic analysis on resource usage (the resource could be memory used or processor time). This allows us to compare two algorithms in terms of best case, worst case and average case behavior. If T(n) is the computation time of the algorithm, then its asymptotic behavior can be expressed as T(n) = O(f(n)) such that T(n) ≤ O(c f(n)), for all n ≥ n The two constants c and n0 are defined such that the algorithm always executes in less that c*f(n) time. 4) What are constant time algorithms? Algorithms that always take a fixed amount of time irrespective of the size of inputs are called constant time algorithms. For example: inserting an element at the head of the linked list. 5) Why is T(n) =c1n2 +c2 n = O(n2)? The computation of the constants is based on the definition of Big-O (see question 3 above): T(n) = c1n2 +c2n ≤ c1n2 +c2n2 (this is true for all n ≥ 1) ≤ (c1+c2)n2 Hence c = c1+c2 and n0 = 1 6) Why cant you compress O(N2 log P + N) to O(N2logP)? We are trying to find the upper bound on the execution time, when we have all terms of the same type, we choose the one with most significance and ignore lesser order terms. In the case of N2logP + N, we do not know which the dominant term is. The N2logP term dominates when N2logP > N. Both terms contribute equally when P = 21/n (assuming the log base is 2), but since we do not know for sure what N and P are, we cannot eliminate the N term. 7) No Mud