Page 15 -

҅࢑ೞח ؘ ೙ਃೠ ࢎ஗ো࢑੄ പࣻח ׮਺җ эणפ׮

↟ ୐ ߣ૩ ঌҊ્ܻ ೐۽Ӓ۔ 1 1 ؔࣅ nߣ
↟ ف ߣ૩ ঌҊ્ܻ ೐۽Ӓ۔ 1 2 ؔࣅ ғࣅ աׅࣅ п ೠ ߣ ୨ ࣁ ߣ

ੑ۱ ௼ӝ n੉ ੘ਸ ٸח ف о૑ ߑߨ੉ ௾ ର੉о ա૑ ঋणפ׮ ೞ૑݅ n੉

ழ૑ݶ ழ૕ࣻ۾ ষ୒դ ର੉о ժפ׮ n 1000੉ غݶ ୐ ߣ૩ ঌҊ્ܻ਷ ؔ
ࣅਸ ୌ ߣ ೧ঠ ೞ޲۽ ࣁ ߣ݅ ҅࢑೧ب غח ف ߣ૩ ঌҊ્ܻҗ ষ୒աѱ ର

੉о ժפ׮
ࠁా ஹೊఠܳ ੉ਊ೧ࢲ ҅࢑ೡ ٸח ੑ۱ ௼ӝ n੉ ݒ਋ ௾ ҃਋о ݆णפ׮
ঌҊ્ܻ ࠙ࢳীࢲח ੑ۱ ௼ӝо ݒ਋ ௾ nী ؀೧ࢲ ٮઉ ࠁח Ѫ੉ ઺ਃ೤פ

׮ ৘ܳ ٜয ਋ܻաۄ ੹ Ҵ޹੄ ಣӐ ա੉ܳ ҅࢑ೞח ޙઁۄҊ ೞݶ ੑ۱ ௼
ӝ n਷ ਋ܻաۄ ੹ Ҵ޹ী ೧׼ೞח 50 000 000੉ ֈח ࣻੑפ׮

6 ؀ޙ੗ 0 ಴ӝߨ ҅࢑ ࠂ੟ب ಴അ

যڃ ঌҊ્ܻ੉ ޙઁܳ ಽӝ ਤ೧ ೧ঠ ೞח ҅࢑੉ ঴݃ա ࠂ੟ೠ૑ աఋմ ੿
بܳ r҅࢑ ࠂ੟ب complexity sۄҊ ೤פ׮ ҅࢑ ࠂ੟بܳ ಴അೞח ߑߨীח ৈ

۞ о૑о ੓חؘ Ӓ ઺ ؀ޙ੗ O ಴ӝߨਸ о੢ ݆੉ ࢎਊ೤פ׮ ؀ޙ੗ O಴
ӝߨ਷ r࠻ য়s ಴ӝߨ੉ۄҊب ࠗܵפ׮

؀ޙ੗ O ಴ӝߨ੄ ੿ഛೠ ੿੄৬ ࢸݺ਷ ੌױ ࢤۚೞҊ খীࢲ ࢓ಝࠄ ৘ઁ ೐
۽Ӓ۔੄ ҅࢑ ࠂ੟بܳ ؀ޙ੗ O۽ ಴ӝೞח ߑߨࠗఠ ࢸݺೞѷणפ׮
୐ ߣ૩ ঌҊ્ܻ਷ ੑ۱ ௼ӝ nী ؀೧ ࢎ஗ ো࢑ ؔࣅ ਸ nߣ ೧ঠ ೤פ׮ ੉

ٸ ੉ ঌҊ્ܻ੄ ҅࢑ ࠂ੟بܳ O(n)੉ۄҊ ಴അ೤פ׮ ೙ਃೠ ҅࢑ പࣻо ੑ
۱ ௼ӝী r੿࠺۹sೡ ٸח O(n)੉ۄҊ ಴അ೤פ׮

ੑ۱ ௼ӝ nী ٮۄ ؔࣅਸ ف ߣঀ ೞח ঌҊ્ܻ੉ ੓׮ݶ যڄөਃ ঴೜ ࢤ
пೞݶ O(2n)ਵ۽ ಴അೡ Ѫ э૑݅ Ӓۧ૑ ঋणפ׮ ੉ٸب ݃ଲо૑۽ Ӓր

O(n)ਵ۽ ಴അ೤פ׮ ؀ޙ੗ O ಴ӝߨ਷ ঌҊ્ܻীࢲ ೙ਃೠ ҅࢑ പࣻܳ ੿
ഛೠ ं੗۽ ಴അೞח Ѫ੉ ইפۄ ੑ۱ ௼ӝ৬੄ ҙ҅۽ ಴അೞӝ ٸޙੑפ׮

ݽف੄ ঌҊ્ܻ XJUI ౵੉ॆ