Obliczanie złożoności czasowej

Witam,
Mam problem z policzeniem złożoności mojego algorytmu, który liczy ilość powtórzeń zadanej wartości w tablicy,. Wykorzystałem wyszukiwanie binarne. Znalazłem w internecie przykładowy filmik gdzie policzona została złożoność czasowa, ale tam była tylko jedna funkcja, mój program na trzy funkcje. Jeśli dobrze rozumiem gdy mamy np. funkcję rekurencyjną zastanawiamy się jaki może być najgorszy przypadek, natomiast nie wiem jak to wygląda jesli mamy trzy funkcje. Trzeba określić najgorszy przypadek dla każdej funkcji oddzielnie, według tego policzyć złożoności funkcji, potem je dodać i określić złożoność ostatecznie dla całego algorytmu?
Np. jeśli miałbym jedną funkcję, która wyszukuje wartość w tablicy, najgorszy przypadek to taki gdy po iluś razach dzielenia listy na pół, algorytmowi zostanie tylko jeden element do sprawdzenia i nie będzie on wartością szukaną. Nie wiem natomiast jak policzyć złożoność dla mojego algorytmu gdzie mam 3 funkcję.
Czy mógłby mi ktoś z tym pomóc?
Kod:

		function licz(tab, w, n)
		{
			//indeks pierwszego wystąpienia "w"
			idMin = pierwszy(tab, 0, n-1, w, n);
			
			//jeśli "w" nie istnieje w tablicy
			if (idMin == -1){return idMin};
			
			//indeks ostatniego wystąpienia
			idMax = ostatni(tab, idMin, n-1, w, n);
			ile = idMax-idMin+1;
			//zwracamy ilość powtórzeń wartości "w"
			return ile;
		}
		
		function pierwszy(tab, l, p, w, n) //indeks pierwszego wystąpienia
		{
			if(l <= p) //l - początek zakresu listy p - koniec zakresu listy
			{
				mid = Math.floor((l+p)/2); //środkowy indeks, zaokrąglamy w dół gdy l;p to lista z parzystą liczbą elementów
				
				if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) //mid == 0 gdy tablica ma 1 element
				{
					return mid; // zwraca indeks pierwszego wystapienia
				}
				else if(w > tab[mid])
				{
					return pierwszy(tab, (mid+1), p, w, n);
				}
				else
				{
					return pierwszy(tab, l, (mid-1), w, n);
				}
			}
			return -1;
		}
		
		function ostatni(tab, l, p, w, n)//indeks ostatniego wystąpienia
		{
			if(l <= p)
			{
				mid2 = Math.floor((l+p)/2);
				
				if((mid2 == n-1 || w < tab[mid2+1]) && (tab[mid2] == w))
				{
					return mid2; //zwraca indeks ostatniego wystąpienia
				}
				else if(w < tab[mid2])
				{
					return ostatni(tab, l, (mid2-1), w, n);
				}
				else
				{
					return ostatni(tab, (mid2+1), p, w, n);
				}
			}
		}

A tutaj filmik gdzie została pokazana metoda liczenia złożoności wyszukiwania binarnego, chciałbym zrobić to tym samym sposobem w moim programie//www.youtube.com/watch?v=TomQQb2kJvc

Troche dziwne pytanie. Masz niby 3 funkcje, ale jedna z nich po prostu woła 2 pozostałe 1 raz więc złożoność to x+y gdzie x to złożoność pierwszego wywołania, a y drugiego. Gdybyś miał tam jakieś n razy wywołaj funkcja() to złożoność byłaby O(n*złożoność_funkcja)
U ciebie z oczywistych względów złożoność obu tych wywołań to O(logn) więc masz O(logn) + O(logn) = O(logn)

Ok, rozumiem. Czyli złożoność drugiej funkcji + złożoność trzeciej. Jeszcze pozostaje kwestia rozpisania jak dojść do tej złożoności - jak policzyć. Tak jak na filmiku, wykorzystano fakt, że najgorsza sytuacja to taka gdy zostaje do przeszukania jeden element i nie jest on równy szukanej wartości. A jak będzie u mnie? Mam znaleźć najgorsze przypadki dla drugiej i trzeciej funkcji oddzielnie?

W każdym wywołaniu tniesz tablicę na pół aż dojdziesz do 1 elementu. Czyli tablica ma n, n/2, n/4, n/8, ..., n/k, ... ,2, 1 elementów. Interesuje cię w takim razie jak długi jest taki ciąg. Na szczęście istnieje funkcja która pozwala taką informacje uzyskać i nazywa się logarytmem w tym przypadku logarytmem przy podstawie 2 z n.
Wynika to z prostego faktu: popatrzmy na ten ciąg odwrotnie -> 1, 2, 4, ... , n/4, n/2, n
Czyli w każdym kroku mnożymy o 2 aż dojdziemy do n. Czyli innymi słowy n = 2^k gdzie k to długość tego ciągu. Interesuje nas jak policzyć k i z definicji logarytmu jeśli n = 2^k to log2(n) = k

Oczywiście możemy mieć n które nie jest potęgą 2 a leży pomiędzy 2^(k-1) i 2^k ale możemy założyć że sobie dopełniamy i bierzemy pesymistyczną wersje z 2^k

Ok, na razie zrobiłem tak:

		function licz(tab, w, n)
		{
			
			idMin = pierwszy(tab, 0, n-1, w, n); ----   t1
			
																		 t - const.
			if (idMin == -1){return idMin}; ----- t2			         L(n) = t1 + t2 + t3 + t4 + t5 = t
			
		
			idMax = ostatni(tab, idMin, n-1, w, n); ---> t3
			ile = idMax-idMin+1; --> t4
		
			return ile; --> t5 
		}
		function pierwszy(tab, l, p, w, n) 
		{
			if(l <= p) ----> c1
			{
				mid = Math.floor((l+p)/2); --> c2
				
				if((mid == 0 || w  > tab[mid-1])&&(tab[mid] == w)) c3	
				{														c - constants
					return mid; ---> c4									G(n) = c1 + c2 + c3 + c4 + c5 + G(n/2) = c + G(n/2)
				}														G(n/2) = c + G(n/4)
																		----------
				else if(w > tab[mid])									G(n) = 2c + G(n/4)
				{														G(n/4) = 2c + G(n/8)
					return pierwszy(tab, (mid+1), p, w, n);				----------
				}														G(n) = 4c + G(n/8)
				
				else													Wzór: G(n) = ic + G(n/2^i)
				{														G(n/2^i) = G(1) // najgorszy przypadek gdy algorytmowi zostanie tylko jeden element do sprawdzenia
					return pierwszy(tab, l, (mid-1), w, n);				             n/(2^i) = 1 => n = 2^i => log_2(n) = i
				}														G(n) = c*log_2(n) + G(n/2^log_2(n)) = c*log_2(n) + G(n/n) = c*log_2(n) + G(1) = z + c*log_2(n)
																		G(n) = log_2(n)
			}
			return -1; ---> c5
		}

Ale nie wiem jak to rozpisać dla funkcji ostatni() ......

Przecież to są ta sama funkcja, chamski copy-paste, niczym się to nie będzie różnić.

Niby tak, ale dla funkcji pierwszy() użyłem zapisu G(n/2^i) = G(1), dzięki czemu mogłem wyliczyć " i " za pomocą n bo G(1) to jakoby złożoność gdy mamy do przeszukania ostatni element tablicy i nie jest on równy szukanemu, ale nie wiem czy dla funkcji ostatni() też mógłbym tak podstawić - to samo?

Możesz spróbować innych metod.
https://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/

Ok, dzięki. Jeszcze jedno pytanie, jaka jest tutaj operacja dominująca(elementarna)? Czy jest to l <= p ? Bo ten warunek określa ile razy każda z dwóch funkcji będzie dzieliła listę na pół.