Expected linear time MST algorithm
ನಿರೀಕ್ಷಿತ ರೇಖೀಯ ಸಮಯ ಎಂ. ಎಸ್. ಟಿ ಅಲ್ಗಾರಿದಮ್ ಯಾವುದೇ ಪ್ರತ್ಯೇಕ ಶೃಂಗಗಳಿಲ್ಲದ ತೂಕದ ಗ್ರಾಫ್ನ ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಅರಣ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಇದನ್ನು ಡೇವಿಡ್ ಕಾರ್ಗರ್, ಫಿಲಿಪ್ ಕ್ಲೈನ್ ಮತ್ತು ರಾಬರ್ಟ್ ಟಾರ್ಜನ್ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಪರಿಶೀಲಿಸುವ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಬೋರುವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ನ ತಂತ್ರಗಳನ್ನು ಅವಲಂಬಿಸಿದೆ. ಇದು ನಿರೀಕ್ಷಿತ ರೇಖೀಯ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಸಾಧಿಸಲು ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಕ್ರಮಾವಳಿಗಳು, ದುರಾಸೆಯ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳ ವಿನ್ಯಾಸ ಮಾದರಿಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ. ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ನಿರ್ಣಾಯಕ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಪ್ರಿಮ್ಸ್ ಅಲ್ಗಾರಿದಮ್, ಕ್ರುಸ್ಕಲ್ಸ್ ಅಲ್ಗಾರಿದಮ್, ರಿವರ್ಸ್-ಡಿಲೀಟ್ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಬೊರುವ್ಕಾಸ್ ಅಲ್ಗಾರಿದಮ್ ಸೇರಿವೆ. ಅವಲೋಕನ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರಮುಖ ಒಳನೋಟವು ಯಾದೃಚ್ಛಿಕ ಮಾದರಿ ಹಂತವಾಗಿದ್ದು, ಇದು ಪ್ರತಿ ಉಪವಿಭಾಗದಲ್ಲಿ ಸೇರಿಸಲು ಯಾದೃಚ್ಛಿಕವಾಗಿ ಅಂಚುಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಗ್ರಾಫ್ ಅನ್ನು ಎರಡು ಉಪವಿಭಾಗಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಪುನರಾವರ್ತಿತವಾಗಿ ಮೊದಲ ಉಪ-ಸಮಸ್ಯೆಯ ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಅರಣ್ಯವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಮರದಲ್ಲಿರದ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಅಂಚುಗಳನ್ನು ತ್ಯಜಿಸಲು ರೇಖೀಯ ಸಮಯ ಪರಿಶೀಲನಾ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಬಳಸುತ್ತದೆ. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲೂ ಗ್ರಾಫ್ನ ಗಾತ್ರವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಬೊರುವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ತೆಗೆದುಕೊಳ್ಳಲಾದ ಕಾರ್ಯವಿಧಾನವನ್ನು ಸಹ ಬಳಸಲಾಗುತ್ತದೆ. ಬೊರೊವ್ಕಾ ಹಂತ ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರತಿಯೊಂದು ಪುನರಾವರ್ತನೆಯು ಬೊರೊವ್ಕಾ ಹಂತ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಬೊರೊವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ನ ರೂಪಾಂತರವನ್ನು ಅವಲಂಬಿಸಿದೆಃ ಇನ್ಪುಟ್ಃ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳಿಲ್ಲದ ಗ್ರಾಫ್ ಜಿ 1 ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ, ವಿ 2 ನಲ್ಲಿ ಹಗುರವಾದ ಅಂಚಿನ ಘಟನೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡಿ '1 ನೇ ಹಂತದಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಅಂಚುಗಳಿಂದ ಸಂಪರ್ಕ ಹೊಂದಿದ ಜಿ ಯ ಪ್ರತಿಯೊಂದು ಘಟಕವನ್ನು ಒಂದೇ ಶೃಂಗದೊಂದಿಗೆ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಸಂಕುಚಿತ ಗ್ರಾಫ್ ಜಿ' ಅನ್ನು ರಚಿಸಿ 3 ಜಿ ಔಟ್ಪುಟ್ನಿಂದ ಎಲ್ಲಾ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳು, ಸ್ವಯಂ-ಲೂಪ್ಗಳು ಮತ್ತು ಕನಿಷ್ಠವಲ್ಲದ ಪುನರಾವರ್ತಿತ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಹಾಕಿಃ ಹಂತ 1 ರಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಅಂಚುಗಳು ಮತ್ತು ಸಂಕುಚಿತ ಗ್ರಾಫ್ ಜಿಎ ಬೊರೊವ್ಕಾ ಹಂತವು ಬೊರೊವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ನ ಆಂತರಿಕ ಲೂಪ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಇದು ಒ (ಎಂ) ಸಮಯದಲ್ಲಿ ಚಲಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಎಂ. ಹೀಗಾಗಿ, ಬೋರುವ್ಕಾ ಹಂತವು ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕನಿಷ್ಠ ಎರಡು ಅಂಶಗಳಿಂದ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಕನಿಷ್ಠ n/2 ಅಂಚುಗಳನ್ನು ಅಳಿಸುತ್ತದೆ, ಅಲ್ಲಿ n ಎಂಬುದು Gಯಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ. ಬೋರುವ್ಕಾ ಹಂತದ ಎಫ್-ಹೆವಿ ಮತ್ತು ಎಫ್-ಲೈಟ್ ಅಂಚುಗಳ ಉದಾಹರಣೆ ಕಾರ್ಯಗತಗೊಳಿಸುವಿಕೆ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಅವುಗಳನ್ನು ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಮರದಿಂದ ಹೊರಗಿಡುವ ನಿರ್ದಿಷ್ಟ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ. ಇವುಗಳನ್ನು ಎಫ್-ಭಾರೀ ಅಂಚುಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಎಫ್-ಭಾರೀ ಅಂಚು ಯು, ವಿ ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಒಂದು ಅಂಚು, ಇದರ ತೂಕವು ಎಫ್ ನಲ್ಲಿ ಯು ನಿಂದ ವಿ ಗೆ ಹೋಗುವ ಮಾರ್ಗದಲ್ಲಿ ಅತಿ ಹೆಚ್ಚು ಅಂಚಿನ ತೂಕಕ್ಕಿಂತ ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. (ಎಫ್ ನಲ್ಲಿ ಒಂದು ಮಾರ್ಗವು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೆ ಅದನ್ನು ಅನಂತ ತೂಕವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ). ಎಫ್-ಭಾರವಿಲ್ಲದ ಯಾವುದೇ ಅಂಚು ಎಫ್-ಲೈಟ್ ಆಗಿರುತ್ತದೆ. ಎಫ್ ಎಂಬುದು ಜಿ ಯ ಉಪವಿಭಾಗವಾಗಿದ್ದರೆ, ಜಿ ಯಲ್ಲಿನ ಯಾವುದೇ ಎಫ್-ಭಾರೀ ಅಂಚು ಸೈಕಲ್ ಗುಣಲಕ್ಷಣದಿಂದ ಜಿ ಯ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಆಗಿರಲು ಸಾಧ್ಯವಿಲ್ಲ. ಅರಣ್ಯವನ್ನು ಗಮನಿಸಿದರೆ, ಎಫ್-ಭಾರೀ ಅಂಚುಗಳನ್ನು ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರದ ಪರಿಶೀಲನಾ ಕ್ರಮಾವಳಿಯನ್ನು ಬಳಸಿಕೊಂಡು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಅಲ್ಗಾರಿದಮ್ ಇನ್ಪುಟ್ಃ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳಿಲ್ಲದ ಗ್ರಾಫ್ ಜಿ, ಜಿ ಖಾಲಿಯಾಗಿದ್ದರೆ, ಖಾಲಿ ಅರಣ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸಿ, ಜಿ ಮೇಲೆ ಎರಡು ಅನುಕ್ರಮವಾದ ಬೊರುವ್ಕಾ ಹಂತಗಳನ್ನು ಚಲಾಯಿಸುವ ಮೂಲಕ ಸಂಕುಚಿತ ಗ್ರಾಫ್ ಜಿ ಅನ್ನು ರಚಿಸಿ. ಅದರ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಅರಣ್ಯ ಎಫ್ ಅನ್ನು ಪಡೆಯಲು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಅನ್ವಯಿಸಿ. ರೇಖೀಯ ಸಮಯದ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರದ ಪರಿಶೀಲನಾ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಜಿ ಯಿಂದ ಎಲ್ಲಾ ಎಫ್-ಭಾರೀ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಹಾಕಿ (ಅಲ್ಲಿ ಎಫ್ ಹಂತ 3 ರಿಂದ ಅರಣ್ಯವಾಗಿದೆ). ಅದರ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಅರಣ್ಯವನ್ನು ಪಡೆಯಲು ಜಿ ಗೆ ಕ್ರಮಾವಳಿಯನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಅನ್ವಯಿಸಿ. ಔಟ್ಪುಟ್ಃ G ಯ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಅರಣ್ಯ ಮತ್ತು ಬೊರುವ್ಕಾ ಹಂತಗಳಿಂದ ಸಂಕುಚಿತ ಅಂಚುಗಳು ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಪ್ರಚೋದನೆಯ ಮೂಲಕ ನಿಖರತೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಲಾಗುತ್ತದೆ. ಮೂಲ ಪ್ರಕರಣವು ಕ್ಷುಲ್ಲಕವಾಗಿ ನಿಜವಾಗಿದೆ. ಟಿ * ಯು ಜಿ ಯ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವಾಗಿರಲಿ. ಬೊರುವ್ಕಾ ಹಂತವೊಂದರಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಪ್ರತಿಯೊಂದು ಅಂಚು ಕಟ್ ಪ್ರಾಪರ್ಟಿಯಿಂದ ಟಿ * ನಲ್ಲಿರುತ್ತದೆ ಮತ್ತು ಸಂಕುಚಿತ ಗ್ರಾಫ್ ಅನ್ನು ರೂಪಿಸಲು ತೆಗೆದುಹಾಕಲಾದ ಯಾವುದೇ ಅಂಚುಗಳು ಕಟ್ ಪ್ರಾಪರ್ಟಿಯಿಂದ (ಅನಗತ್ಯ ಅಂಚುಗಳಿಗೆ) ಮತ್ತು ಸೈಕಲ್ ಪ್ರಾಪರ್ಟಿಯಿಂದ (ಸ್ವಯಂ ಲೂಪ್ಗಳಿಗೆ) ಟಿ * ನಲ್ಲಿರುವುದಿಲ್ಲ. ಹಂತ 2 ರಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡದ ಟಿ * ನ ಉಳಿದ ಅಂಚುಗಳು ಕಟ್ ಪ್ರಾಪರ್ಟಿಯಿಂದ ಸಂಕುಚಿತ ಗ್ರಾಫ್ನ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ರೂಪಿಸುತ್ತವೆ (ಪ್ರತಿ ಕಟ್ ಸೂಪರ್ನೋಡ್ ಆಗಿರಲಿ). ತೆಗೆದುಹಾಕಲಾದ ಪ್ರತಿ ಎಫ್-ಭಾರೀ ಅಂಚು ಸೈಕಲ್ ಗುಣಲಕ್ಷಣದಿಂದ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀಯಲ್ಲಿರುವುದಿಲ್ಲ. ಅಂತಿಮವಾಗಿ ಎಫ್ 'ಎಂಬುದು ಇಂಡಕ್ಟಿವ್ ಹೈಪೋಥೆಸಿಸ್ನಿಂದ ಸಂಕುಚಿತ ಗ್ರಾಫ್ನ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಆಗಿದೆ. ಹೀಗಾಗಿ ಎಫ್ 'ಮತ್ತು ಬೊರುವ್ಕಾ ಮೆಟ್ಟಿಲುಗಳಿಂದ ಸಂಕುಚಿತವಾದ ಅಂಚುಗಳು ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಕಾರ್ಯಕ್ಷಮತೆ ನಿರೀಕ್ಷಿತ ಕಾರ್ಯಕ್ಷಮತೆಯು ಯಾದೃಚ್ಛಿಕ ಮಾದರಿ ಹಂತದ ಫಲಿತಾಂಶವಾಗಿದೆ. ಯಾದೃಚ್ಛಿಕ ಮಾದರಿ ಹಂತದ ಪರಿಣಾಮಕಾರಿತ್ವವನ್ನು ಈ ಕೆಳಗಿನ ಲೆಮ್ಮಾದಿಂದ ವಿವರಿಸಲಾಗಿದೆ, ಇದು ಜಿ ಯಲ್ಲಿ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಬಂಧವನ್ನು ಇರಿಸುತ್ತದೆ ಮತ್ತು ಆ ಮೂಲಕ ಎರಡನೇ ಉಪ-ಸಮಸ್ಯೆಯ ಗಾತ್ರವನ್ನು ನಿರ್ಬಂಧಿಸುತ್ತದೆ. ಯಾದೃಚ್ಛಿಕ ಮಾದರಿ ಲೆಮ್ಮಾ ಲೆಮ್ಮಾ-ಎಚ್ ಎಂಬುದು ಜಿ ಯ ಪ್ರತಿ ತುದಿಯನ್ನು ಸ್ವತಂತ್ರವಾಗಿ ಸಂಭವನೀಯತೆ ಪಿ ಯೊಂದಿಗೆ ಸೇರಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಜಿ ಯ ಉಪವಿಭಾಗವಾಗಿರಲಿ ಮತ್ತು ಎಫ್ ಎಚ್ ನ ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಅರಣ್ಯವಾಗಿರಲಿ. ಜಿ ಯಲ್ಲಿ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಎನ್/ಪಿ ಆಗಿರುತ್ತದೆ, ಅಲ್ಲಿ ಎನ್ ಜಿ ಯಲ್ಲಿ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಲೆಮ್ಮಾವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಜಿ ಯ ಅಂಚುಗಳನ್ನು ಎಚ್ ಗೆ ಸೇರಿಸಲಾಗುತ್ತಿರುವುದನ್ನು ಪರೀಕ್ಷಿಸಿ. ಜಿ ಯಲ್ಲಿನ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಎಚ್ ನ ಅಂಚುಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಕ್ರಮದಿಂದ ಸ್ವತಂತ್ರವಾಗಿದೆ ಏಕೆಂದರೆ ಎಲ್ಲಾ ಆಯ್ಕೆ ಆದೇಶಗಳಿಗೆ ಕನಿಷ್ಠ ವ್ಯಾಪಿಸಿರುವ ಅರಣ್ಯ ಎಚ್ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಪುರಾವೆಯ ಸಲುವಾಗಿ, ಅಂಚಿನ ತೂಕದ ಕ್ರಮದಲ್ಲಿ ಒಂದು ಸಮಯದಲ್ಲಿ ಜಿ ಒಂದರ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ಎಚ್ಗೆ ಅಂಚುಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದನ್ನು ಪರಿಗಣಿಸಿ. ಇ ಅನ್ನು ಪ್ರಸ್ತುತ ಅಂಚು ಎಂದು ಪರಿಗಣಿಸೋಣ. e ನ ಕೊನೆಯ ಬಿಂದುಗಳು H ನ ಎರಡು ಸಂಪರ್ಕ ಕಡಿತಗೊಂಡ ಘಟಕಗಳಲ್ಲಿದ್ದರೆ, e ಆ ಘಟಕಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಹಗುರವಾದ ಅಂಚು ಮತ್ತು ಅದನ್ನು H ಗೆ ಸೇರಿಸಿದರೆ ಅದು ಕಟ್ ಪ್ರಾಪರ್ಟಿಯಿಂದ F ನಲ್ಲಿರುತ್ತದೆ. ಇದರರ್ಥ ಇ ಅನ್ನು ಎಚ್ಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆಯೋ ಇಲ್ಲವೋ ಎಂಬುದನ್ನು ಲೆಕ್ಕಿಸದೆ ಎಫ್-ಲೈಟ್ ಆಗಿದೆ, ಏಕೆಂದರೆ ಭಾರವಾದ ಅಂಚುಗಳನ್ನು ಮಾತ್ರ ತರುವಾಯ ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. e ನ ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳು H ನ ಒಂದೇ ಘಟಕದಲ್ಲಿದ್ದರೆ ಅದು ಚಕ್ರದ ಗುಣಲಕ್ಷಣದಿಂದ ಎಫ್-ಭಾರವಾಗಿರುತ್ತದೆ (ಮತ್ತು ಯಾವಾಗಲೂ ಇರುತ್ತದೆ). ಎಡ್ಜ್ ಇ ಅನ್ನು ನಂತರ ಸಂಭವನೀಯತೆ ಪಿ ಯೊಂದಿಗೆ ಎಚ್ ಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಎಚ್ ಗೆ ಸೇರಿಸಲಾದ ಎಫ್-ಲೈಟ್ ಅಂಚುಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯು ಎನ್-1 ಆಗಿರುತ್ತದೆ ಏಕೆಂದರೆ ಎಚ್ ನ ಯಾವುದೇ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವು ಎನ್-1 ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಮ್ಮೆ ಎನ್-1 ಎಫ್-ಲೈಟ್ ಅಂಚುಗಳನ್ನು ಎಚ್ಗೆ ಸೇರಿಸಿದ ನಂತರ, ಸೈಕಲ್ ಗುಣಲಕ್ಷಣದಿಂದ ಪರಿಗಣಿಸಲಾದ ನಂತರದ ಯಾವುದೇ ಅಂಚುಗಳು ಎಫ್-ಲೈಟ್ ಆಗಿರುವುದಿಲ್ಲ. ಹೀಗಾಗಿ, ಜಿ ನಲ್ಲಿನ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ವಾಸ್ತವವಾಗಿ ಎಚ್ ಗೆ ಎನ್-1 ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳನ್ನು ಸೇರಿಸುವ ಮೊದಲು ಎಚ್ ಗೆ ಪರಿಗಣಿಸಲಾದ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಿಂದ ಸೀಮಿತವಾಗಿದೆ. ಯಾವುದೇ ಎಫ್-ಬೆಳಕಿನ ಅಂಚನ್ನು ಸಂಭವನೀಯತೆ ಪಿ ಯೊಂದಿಗೆ ಸೇರಿಸಲಾಗಿರುವುದರಿಂದ ಇದು ಎನ್-1 ತಲೆಗಳು ಕಾಣಿಸಿಕೊಳ್ಳುವವರೆಗೆ ತಲೆಗಳು ಬರುವ ಸಂಭವನೀಯತೆ ಪಿ ಹೊಂದಿರುವ ನಾಣ್ಯವನ್ನು ತಿರುಗಿಸುವುದಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ನಾಣ್ಯ ಫ್ಲಿಪ್ಪುಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯು Gಯಲ್ಲಿನ F-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ನಾಣ್ಯ ಫ್ಲಿಪ್ಪುಗಳ ಸಂಖ್ಯೆಯ ವಿತರಣೆಯನ್ನು n-1 ಮತ್ತು p ನಿಯತಾಂಕಗಳೊಂದಿಗೆ ವಿಲೋಮ ದ್ವಿಪದ ವಿತರಣೆಯಿಂದ ನೀಡಲಾಗುತ್ತದೆ. ಈ ನಿಯತಾಂಕಗಳಿಗೆ ಈ ವಿತರಣೆಯ ನಿರೀಕ್ಷಿತ ಮೌಲ್ಯವು (n-1)/p ಆಗಿದೆ. ನಿರೀಕ್ಷಿತ ವಿಶ್ಲೇಷಣೆ ಪುನರಾವರ್ತಿತ ಉಪ-ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಮಾಡಿದ ಕೆಲಸವನ್ನು ನಿರ್ಲಕ್ಷಿಸುವುದರಿಂದ ಅಲ್ಗಾರಿದಮ್ನ ಒಂದೇ ಆಹ್ವಾನದಲ್ಲಿ ಮಾಡಿದ ಒಟ್ಟು ಕೆಲಸದ ಪ್ರಮಾಣವು ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ. ಹಂತ 1 ಸ್ಥಿರವಾದ ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಬೋರುವ್ಕಾ ಹಂತದ ವಿಭಾಗದಲ್ಲಿ ಉಲ್ಲೇಖಿಸಿರುವಂತೆ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಸಮಯ ರೇಖೀಯವಾಗಿ ಬೋರುವ್ಕಾ ಹಂತಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಹಂತ 3 ಅಂಚುಗಳ ಮೂಲಕ ಪುನರಾವರ್ತಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರತಿಯೊಂದಕ್ಕೂ ಒಂದೇ ನಾಣ್ಯವನ್ನು ತಿರುಗಿಸುತ್ತದೆ ಆದ್ದರಿಂದ ಇದು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ. ಮಾರ್ಪಡಿಸಿದ ರೇಖೀಯ ಸಮಯದ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ವೆರಿಫಿಕೇಶನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಹಂತ 4 ಅನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಅಲ್ಗಾರಿದಮ್ನ ಒಂದು ಪುನರಾವರ್ತನೆಯಲ್ಲಿ ಮಾಡಲಾದ ಕೆಲಸವು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿರುವುದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ನ ಒಂದು ಸಂಪೂರ್ಣ ಓಟದಲ್ಲಿ (ಎಲ್ಲಾ ಪುನರಾವರ್ತಿತ ಕರೆಗಳನ್ನು ಒಳಗೊಂಡಂತೆ) ಮಾಡಲಾದ ಕೆಲಸವು ಮೂಲ ಸಮಸ್ಯೆಯಲ್ಲಿನ ಒಟ್ಟು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯ ಸ್ಥಿರ ಅಂಶದಿಂದ ಮತ್ತು ಎಲ್ಲಾ ಪುನರಾವರ್ತಿತ ಉಪ-ಸಮಸ್ಯೆಗಳಿಂದ ಸೀಮಿತವಾಗಿರುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರತಿಯೊಂದು ಆಹ್ವಾನವು ಗರಿಷ್ಠ ಎರಡು ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಉಂಟುಮಾಡುತ್ತದೆ ಆದ್ದರಿಂದ ಉಪ-ಸಮಸ್ಯೆಗಳ ಸಮೂಹವು ಅವಳಿ ಮರವನ್ನು ರೂಪಿಸುತ್ತದೆ. ಪ್ರತಿ ಬೋರುವ್ಕಾ ಹಂತವು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕನಿಷ್ಠ ಎರಡು ಅಂಶಗಳಿಂದ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ ಆದ್ದರಿಂದ ಎರಡು ಬೋರುವ್ಕಾ ಹಂತಗಳ ನಂತರ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಾಲ್ಕು ಅಂಶಗಳಿಂದ ಕಡಿಮೆ ಮಾಡಲಾಗಿದೆ. ಹೀಗಾಗಿ, ಮೂಲ ರೇಖಾಚಿತ್ರವು n ಶೃಂಗಗಳು ಮತ್ತು m ಅಂಚುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಮರದ d ಆಳದಲ್ಲಿ ಪ್ರತಿ ಉಪಪ್ರಶ್ನೆ ಗರಿಷ್ಠ n/4d ಶೃಂಗಗಳ ರೇಖಾಚಿತ್ರದಲ್ಲಿರುತ್ತದೆ. ಮರವು ಹೆಚ್ಚಿನ ಲಾಗ್ 4 ಎನ್ ಮಟ್ಟವನ್ನು ಹೊಂದಿದೆ. ಪುನರಾವರ್ತಿತ ಮರದ ಬಗ್ಗೆ ತರ್ಕಿಸಲು 3ನೇ ಹಂತದ ಪುನರಾವರ್ತಿತ ಕರೆಯಲ್ಲಿ ಎಡ ಮಗುವಿನ ಸಮಸ್ಯೆಯು ಉಪ-ಸಮಸ್ಯೆಯಾಗಿರಲಿ ಮತ್ತು 5ನೇ ಹಂತದ ಪುನರಾವರ್ತಿತ ಕರೆಯಲ್ಲಿ ಬಲ ಮಗುವಿನ ಸಮಸ್ಯೆಯು ಉಪ-ಸಮಸ್ಯೆಯಾಗಿರಲಿ. ಮರದ ಪ್ರತಿ ಎಡ ಪಥದಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುವ ಮೂಲಕ ಮೂಲ ಸಮಸ್ಯೆಯಲ್ಲಿನ ಒಟ್ಟು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮತ್ತು ಎಲ್ಲಾ ಉಪ-ಸಮಸ್ಯೆಗಳನ್ನು ಎಣಿಸಿ. ಎಡ ಮಾರ್ಗವು ಬಲ ಚೈಲ್ಡ್ ಅಥವಾ ಮೂಲದಿಂದ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಎಡ ಮಕ್ಕಳ ಮಾರ್ಗದ ಮೂಲಕ ತಲುಪಬಹುದಾದ ಎಲ್ಲಾ ನೋಡ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಬಲಭಾಗದಲ್ಲಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಅವಳಿ ಮರದ ಎಡಭಾಗದ ಪಥಗಳನ್ನು ನೀಲಿ ಬಣ್ಣದಲ್ಲಿ ಸುತ್ತುವಂತೆ ತೋರಿಸಲಾಗಿದೆ. ಎಡ ಮಗುವಿನ ಸಮಸ್ಯೆಯ ಪ್ರತಿಯೊಂದು ತುದಿಯನ್ನು ಅದರ ಮೂಲ ಸಮಸ್ಯೆಯ ಅಂಚುಗಳಿಂದ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ (ಬೊರುವ್ಕಾ ಹಂತಗಳಲ್ಲಿ ಸಂಕುಚಿತಗೊಂಡ ಅಂಚುಗಳನ್ನು ಕಡಿಮೆ) ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ 1/2. ಮೂಲ ಸಮಸ್ಯೆಯು x ಅಂಚುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಎಡ ಮಗುವಿನ ಸಮಸ್ಯೆಯಲ್ಲಿ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ x/2 ಆಗಿರುತ್ತದೆ. x ಅನ್ನು ಯಾದೃಚ್ಛಿಕ ವೇರಿಯೇಬಲ್ X ನಿಂದ ಬದಲಾಯಿಸಿದರೆ, ನಿರೀಕ್ಷೆಯ ರೇಖೀಯತೆಯಿಂದ ಎಡ ಚೈಲ್ಡ್ ಸಮಸ್ಯೆ Y ಯಲ್ಲಿ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಹೀಗಾಗಿ ಎಡ ಮಾರ್ಗದ ಮೇಲ್ಭಾಗದಲ್ಲಿರುವ ಸಮಸ್ಯೆಯಲ್ಲಿ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು k ಆಗಿದ್ದರೆ, ಎಡ ಮಾರ್ಗದಲ್ಲಿನ ಪ್ರತಿ ಉಪಪ್ರಶ್ನೆಗಳಲ್ಲಿನ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯ ಮೊತ್ತವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ (ಜ್ಯಾಮಿತೀಯ ಸರಣಿಯನ್ನು ನೋಡಿ). ಮೂಲವು m ಅಂಚುಗಳನ್ನು ಹೊಂದಿದೆ ಆದ್ದರಿಂದ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು 2m ಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಬಲ ಉಪಪ್ರಶ್ನೆಗಳಲ್ಲಿ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳಿಗಿಂತ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಬಲ ಉಪ-ಸಮಸ್ಯೆಯಲ್ಲಿನ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು ಮೂಲ ಸಮಸ್ಯೆಯಲ್ಲಿನ ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಅಲ್ಲಿ ಎಫ್ ಎಡ ಉಪ-ಸಮಸ್ಯೆಯ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವಾಗಿದೆ. ಎಫ್-ಬೆಳಕಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಮಾದರಿ ಲೆಮ್ಮಾದಿಂದ ಉಪ-ಸಮಸ್ಯೆಯಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗಿಂತ ಎರಡು ಪಟ್ಟು ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿರುತ್ತದೆ. d ಆಳದಲ್ಲಿರುವ ಉಪ-ಸಮಸ್ಯೆಯಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯು n/4d ಆಗಿರುವುದರಿಂದ ಎಲ್ಲಾ ಸರಿಯಾದ ಉಪ-ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಟ್ಟು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೀಗೆ ನೀಡಲಾಗಿದೆ. ಹೀಗಾಗಿ, ಮೂಲ ಸಮಸ್ಯೆಯಲ್ಲಿ ಮತ್ತು ಎಲ್ಲಾ ಉಪ-ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಅಂಚುಗಳ ನಿರೀಕ್ಷಿತ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 2 ಮೀ + ಎನ್ ಆಗಿರುತ್ತದೆ. ಯಾವುದೇ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳಿಲ್ಲದ ಗ್ರಾಫ್ಗೆ n ಗರಿಷ್ಠ 2m ಆಗಿರುವುದರಿಂದ ಅಲ್ಗಾರಿದಮ್ ನಿರೀಕ್ಷಿತ ಸಮಯ O (m) ನಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಕೆಟ್ಟ ಕೇಸ್ ವಿಶ್ಲೇಷಣೆ ಅತ್ಯಂತ ಕೆಟ್ಟ ಕೇಸ್ ರನ್ಟೈಮ್ ಬೋರ್ವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ನ ರನ್ಟೈಮ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಆಹ್ವಾನದ ಎಡ ಅಥವಾ ಬಲ ಉಪಪ್ರಶ್ನೆಗಳಿಗೆ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಸೇರಿಸಿದರೆ ಇದು ಸಂಭವಿಸುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ ಅಲ್ಗಾರಿದಮ್ ಬೋರುವ್ಕಾದ ಅಲ್ಗಾರಿದಮ್ಗೆ ಹೋಲುತ್ತದೆ, ಇದು n ಶೃಂಗಗಳು ಮತ್ತು m ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ನಲ್ಲಿ O (ಕನಿಷ್ಠ {n2, mlogn}) ನಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಮತ್ತಷ್ಟು ಓದುವಿಕೆ ಲೀನಿಯರ್ ಟೈಮ್ ಯಾದೃಚ್ಛಿಕ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಪರಿಶೀಲನೆ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ