2.11 DSA

 

 

 

이거랑(BinarySearchTree)... 그다음 배운거는 재귀. 

 

T(n) = T(n-k) + k*c 

 

관련해서 지피티의 설명. 

 

Got it! Your professor is likely explaining how to analyze the time complexity of recursive linear search using recurrence relations. Let’s go through this step by step. 🚀

---

Step 1: Understanding Recursive Linear Search

The recursive linear search function looks something like this:

java

CopyEdit

boolean linearSearch(int[] arr, int start, int elem) { if (start > arr.length - 1) return false; if (arr[start] == elem) return true; return linearSearch(arr, start + 1, elem); }

Each recursive call processes one element and moves to the next index (start + 1). The problem size reduces by 1 each time.

---

Step 2: Setting Up the Recurrence Relation

Let’s define T(n)T(n)T(n) as the time taken to search in an array of size nnn.

1. If the element is found at the first position (base case), the function returns immediately. This takes constant time O(1)O(1)O(1).T(1)=cT(1) = cT(1)=c
2. If the element is not found at the first position, the function calls itself on the remaining n−1n-1n−1 elements:T(n)=T(n−1)+cT(n) = T(n-1) + cT(n)=T(n−1)+cHere, ccc represents the constant time work done at each step (checking arr[start]).

---

Step 3: Expanding the Recurrence Relation

We substitute the recurrence multiple times:

T(n)=T(n−1)+cT(n) = T(n-1) + cT(n)=T(n−1)+c T(n−1)=T(n−2)+cT(n-1) = T(n-2) + cT(n−1)=T(n−2)+c T(n−2)=T(n−3)+cT(n-2) = T(n-3) + cT(n−2)=T(n−3)+c ⋮\vdots⋮ T(2)=T(1)+cT(2) = T(1) + cT(2)=T(1)+c

Now, substituting all these:

T(n)=T(n−1)+cT(n) = T(n-1) + cT(n)=T(n−1)+c =(T(n−2)+c)+c= (T(n-2) + c) + c=(T(n−2)+c)+c =(T(n−3)+c)+c+c= (T(n-3) + c) + c + c=(T(n−3)+c)+c+c =T(1)+(n−1)⋅c= T(1) + (n-1) \cdot c=T(1)+(n−1)⋅c

Since T(1)T(1)T(1) is just a constant, we simplify:

T(n)=O(n)T(n) = O(n)T(n)=O(n)

Thus, the time complexity of recursive linear search is O(n)O(n)O(n), which is linear time.

 

 

Binary Search

 

 

T(n) = T(n/2)+c

 

 

T(n) = T(n/ 2^k) + k*c 

T(1) = C1

n / 2^k = 1 

k = log n 

 

그래서 Logn 이 된다.  (?) 

T(n) = T(1) + c * log n 

그래서 Theta(logn)