[ Home Page ] [ Back ] [ Content of Contributions ] [ Movement: Green Leaf World ]
Algorithm: Linear Search(A, N, X, Loc)Best Case: X is at 0th index.
Complexity: Ω (1)
Worst Case: X is not present.
Complexity: O (N)
Algorithm: Binary Search(A, N, X, Loc)
Best Case: X is at (N-1)/2 index.
Complexity: Ω (1)
Worst Case: X is not present.
Complexity: O (log N)
Derivation:
T(N)= 1+ T(N/2)
= 1+ (1+ T(N/4))
= 2+ T(N/4)
= 3+ T(N/8)
.
.
.
= k+ T(N/(2^k)) [ for some K, N<=(2^k), so, k= log N ]
= log N
Algorithm: Quick Sort (A, N)
Best Case: Every pivot is splitting the list into equal two segments.
Complexity: Ω (N*log N)
Derivation:
T(N)= N+ {2*T(N/2)}
= N+ 2*[(N/2) + {2*T(N/4)}]
= N+ 2*(N/2) + 4*T(N/4)
= 2N+ 4T(N/4)
= 2N+ 4*[(N/4) + {2*T(N/8)]
= 3N+ 8T(N/8)
.
.
.
= kN+ (2^k)*T(N/(2^k)) [ for some K, N<=(2^k), so, k= log N ]
= (log N)*N + N
= N(log N + 1)
≈ N * log N
Worst Case: Data is already arranged in some order.
Complexity: O (N*N)
