spaceTimeComplexity.txt

Bubble Sort:

Time Complexity:
Best Case: O(n) - when the list is already sorted.
Worst Case: O(n^2) - when the list is in reverse order.
Average Case: O(n^2)

Space Complexity: O(1) - Bubble sort is an in-place sorting algorithm.

-> Simple and easy to implement, therefore suitable for smaller datasets
-> Performs very well when data is partially/nearly sorted but efficiency is lower to Insertion Sort 
-> In-place sorting algorithm meaning they do not require additional memory proportional to the size of the input

************************************************************************

Insertion Sort:

Time Complexity:
Best Case: O(n) - when the list is nearly sorted.
Worst Case: O(n^2) - when the list is in reverse order.
Average Case: O(n^2)

Space Complexity: O(1) - Insertion sort is an in-place sorting algorithm.

-> Simple and easy to implement, therefore suitable for smaller datasets
-> Performs very well when data is nearly/partially sorted ***
-> Not the most efficient algorithm for large datasets
-> In-place sorting algorithm meaning they do not require additional memory proportional to the size of the input

************************************************************************


Selection Sort:

Time Complexity:
Best Case: O(n^2) - no best case advantage.
Worst Case: O(n^2) - regardless of the input.
Average Case: O(n^2)

Space Complexity: O(1) - Selection sort is an in-place sorting algorithm.

-> Suitable for or small datasets or situations where simplicity and ease of implementation are more important 
   than the efficiency of the sorting process
-> Generally, used in educational settings.
-> In practial setting, opt for other algorithms.

************************************************************************

Merge Sort:

Time Complexity:
Best Case: O(n log n) - when the input is divided evenly.
Worst Case: O(n log n) - always, because it consistently divides the input in half.
Average Case: O(n log n)

Space Complexity: O(n) - Merge sort typically requires additional space for the merging process.

-> Best suitable for large datasets
-> Well-suited for linked lists and external sorting (when data too large to fit into memory)
-> Consistent O(n log n) time complexity

************************************************************************


Quick Sort:

Time Complexity:
Best Case: O(n log n) - when the pivot always divides the array into two equal halves. (Same complexity with/without sorted)
Worst Case: O(n^2) - when the pivot consistently results in unbalanced partitions.
Average Case: O(n log n)

Space Complexity: O(log n) - Quick sort is generally an in-place sorting algorithm, but its space complexity is influenced by the recursion depth

Best suitable for large datasets
-> In-place sort (requires only constant amount of additional memory)	
-> Worst-case time complexity is O(n^2) (rare in pracice with good pivot selection strategies)
		Note: Good-pivot selection strategies include selecting the first, last or middle.


************************************************************************

Radix Sort:

Space complexity 
O(n+k) 
where, n is the number of elements in the array and k is the range of the input

Time Complexity
O(nk)

->Radix sort is a non-comparative sorting algorithm
->Its efficiency is often dependent on the characteristics of the input data
->It performs well when the range of the input is not significantly larger than the number of elements 
 and when the distribution of elements across digits is relatively uniform.
 
************************************************************************
************************************************************************


---Key Highlights---

1. Compare the Worst Case of each sorting algorithm. 
2. Compare the Worst Case of each searching algorithm.
3. What is the most efficient/ sorting algorithm for smaller data sets?
4. What is the most efficient sorting algorithm for larger data sets?

5. Which sorting algorithm has a worst-case time complexity of O(n^2) in its basic form "fundamental version"? 
	a.Quicksort	 	b.Mergesort 	c.Heapsort 	d.Bubblesort
	
6. In the worst-case scenario, which of the following sorting algorithms exhibits a time complexity of O(n log n)?
	a.Bubblesort  	b.Insertion sort  	c.Quicksort  	d.Counting sort
	
7. Which sorting algorithm is known for its stable O(n log n) performance in the worst case?
	a. Bubblesort	b. Mergesort	c. Heapsort		d. Shellsort

8. What is the worst-case time complexity of the quicksort algorithm when choosing the pivot poorly in each partitioning step?
	a. O(n)			b. O(n log n)	c. O(n^2)		d. O(log n)
	
9. In the worst-case scenario, which of the following sorting algorithms has a time complexity that depends on the initial order of the input data?
	a. Mergesort	b. Shellsort	c. Bubblesort	d. Radix sort
	
10. Which sorting algorithm has a worst-case time complexity of O(n log n) but may require additional space for its operation?
	a. Bubblesort	b. Quicksort	c. Radix sort	d. Mergesort

11. In the worst case, which of the following sorting algorithms has a time complexity of O(n^2) but can be optimized with adaptive techniques?
	a. Insertion sort	b. Shellsort	c. Mergesort	d. Heapsort
	
 



Insertion Sort/Bubble Sort 			 |				Merge Sort/Quick Sort
-> small no. of elements 			 | 				->	larger no. of elements

Merge Sort							 |			    Quick Sort
-> O(log n) worst case			     |				-> O(n^2) worst case	
-> O(n) space complexity			 |				-> O(log n) space complexity influenced by the recursion depth


Insertion Sort 						 |				Bubble Sort
->best for nearly/partially sorted	 |			    ->compared to Insertion Sort, less efficiency for nearly/partially sorted


---------------------------------------------------------

# Sorting algorithm known for its stablity: Merge Sort
# The primary advantage of Radix Sort over comparison-based sorting algorithms: Not affected by the initial order of the input
# In place sorting algorithm: O(1) space complexity: Bubble and Insertion Sort
# QuickSort perform poorly? : Already sorted Data 
	Reason:	
		This is because QuickSort's partitioning strategy involves selecting a pivot element and partitioning the array into two sub-arrays
		such that elements less than the pivot are on the left and elements greater than the pivot are on the right. 
		If the data is already sorted or nearly sorted, there's a higher probability that the pivot chosen is the smallest or largest element,
		leading to unbalanced partitions.
		
		In this case, the worst case O(n^2) is the time complexity due to unbalanced partition.


************************************************************************

O(1)
Insertion/Removal from LinkedList, HashSet, HashMap
Searching in hash table based
In-place sorting algorithm: Bubble Sort and Insertion Sort

O(n)
Insertion/Removal in Array-Based
Searching in LinkedList
Space Complexity of Merge Sort


O(log n)
Insertion/Removal and searching in a Binary-Type Tree
TreeSet or TreeMap
Space complexity of Quick Sort

O(n log n)
Average Time Complexity: Sorting in Quick and Merge Sort

**********************************************************

Notation						Name 						        (put n=32)
O(1)							constant time				         1
O(log n)  						logarithmic					 	     5
O(n)							linear						 		 32
O(n log n)						linearithmic				         160
O(n^2)							quadratic					 		 1024						nested for loop
O(n^3)							cubic					        	 32768						nested for loop 
O(2^n) 							exponential 				         4294967296


-----------------------
Answers: 
1 d. Bubblesort
2 c. Quicksort
3 b. Mergesort
4 c. O(n^2)
5 c. Bubblesort
6 d. Mergesort
7 a. Insertion sort