CoE KKU

การใช้ทรัพยากรที่สำคัญที่สุดที่ต้องทำการวิเคราะห์ คือ running time มีปัจจัยหลายอย่างที่มีผลต่อ running time ของโปรแกรม ปัจจัยบางอย่างเช่น compiler และ computer ที่ใช้ก็ไม่เกี่ยวข้องกับโมเดลที่เราได้กล่าวไปแล้ว ดังนั้นจะไม่กล่าวถึงในที่นี้ ปัจจัยอื่นที่สำคัญ คือ ตัวอัลกอริทึมที่ใช้เองและอินพุตที่ใช้ในอัลกอริทึมนั้น ๆ และโดยทั่วไปแล้วขนาดของอินพุตเป็นสิ่งที่เราจะให้ความสนใจเป็นเรื่องหลัก

เรากำหนดนิยามสำหรับฟังก์ชัน 2 ตัว คือ $T_{avg}(n)$ สำหรับ average case running time และ $T_{worst}(n)$ สำหรับ worst-case running time ของอัลกอริทึมที่ใช้สำหรับอินพุตที่มีขนาดเป็น n และปกติแล้ว $T_{avg}(n) < T_{worst}(n)$

ถ้าอัลกอริทึมมีหลายอินพุตฟังก์ชันดังกล่าวนี้อาจมีหลาย arguments ได้

บางครั้งอาจจะมีการกล่าวถึงการวิเคราะห์อัลกอริทึมในกรณี best-case เช่นกันแต่จะไม่ค่อยได้ประโยชน์นัก ทั้งนี้เนื่องจากมันไม่สามารถนำมาใช้เป็นตัวแทนของพฤติกรรมของอัลกอริทึมได้ ในขณะที่ประสิทธิภาพในกรณี worst-case จะสามารถใช้เป็นตัวแทนพฤติกรรมของอัลกอริทึมสำหรับขนาดอินพุตใด ๆ ก็ได้

โดยทั่วไปแล้วค่าที่ต้องหา คือ worst-case time ยกเว้นบางกรณีเท่านั้น ด้วยเหตุว่ามันสามารถใช้เป็นขอบเขตเวลาได้กับทุกขนาดอินพุต ซึ่ง average-case time ไม่สามารถใช้ได้ อีกทั้งตัวนิยามของคำ average เองก็จะมีผลต่อการวิเคราะห์ (ดังตัวอย่างข้างหน้านี้ที่ไม่สามารถกำหนดนิยามของคำ average ที่แน่นอนได้)

ตัวอย่างปัญหา MAXIMUM SUBSEQUENCE SUM:

กำหนดเลขจำนวนเต็มให้ (อาจเป็นค่าลบได้) เป็น $a_1, a_2, . . . , a_n$ หาค่าที่มากที่สุดของ $∑_{k=i}^jA_k$ (เพื่อความสะดวก กำหนดให้ maximum subsequence sum มีค่าเป็น 0 ถ้าค่าที่กำหนดให้ทั้งหมดมีค่าติดลบ) เช่น: อินพุต -2, 11, -4, 13, -5, -2, จะได้คำตอบ 20 ($a_2$ ถึง $a_4$) ปัญหานี้เป็นปัญหาที่น่าสนใจทั้งนี้เนื่องจากมีอัลกอริทึมหลายแบบที่ใช้แก้ปัญหานี้ได้ และแต่ละอัลกอริทึมก็มีประสิทธิภาพแตกต่างกันมาก เราจะกล่าวถึงอัลกอริทึม 4 แบบ รูปที่ 2.3 แสดงเวลา running time ของอัลกอริทึมที่ทำงานบนเครื่องคอมพิวเตอร์

รูปที่ 2.3 Running time ของอัลกอริทึมทั้ง 4 (in second) ของปัญหา maximum subsequence sum

จากตารางรูปที่ 2.3 จะเห็นว่าสำหรับกรณีที่อินพุตมีจำนวนไม่มาก อัลกอริทึมทั้ง 4 ใช้เวลาในการทำงานน้อยมากเหมือน ๆ กัน ดังนั้นก็ไม่จำเป็นต้องใช้ความพยายามในการคิดหาหรือออกแบบอัลกอริทึมให้ยุ่งยาก อย่างไรก็ตามมีโปรแกรมในอดีตจำนวนมากที่เขียนขึ้นด้วยการใช้อัลกอริทึมที่อยู่บนสมมุติฐานว่าจำนวนข้อมูลมีปริมาณน้อยซึ่งไม่เป็นจริงในภาวะปัจจุบัน และ จำเป็นต้องเขียนโปรแกรมขึ้นใหม่เนื่องจากปริมาณข้อมูลเพิ่มจำนวนขึ้นมากจนอัลกอริทึมเดิมไม่สามารถทำงานอย่างมีประสิทธิภาพได้ อีกประการหนึ่งคือ เวลาที่แสดงในตารางไม่ได้นับรวมเวลาในการอ่านข้อมูลอินพุต กล่าวสำหรับอัลกอริทึมที่ 4 แล้ว เพียงเฉพาะเวลาที่ต้องใช้ในการอ่านค่าจากจานแม่เหล็กก็จะมากกว่าเวลาที่ต้องใช้ในการแก้ปัญหาหลายเท่า อัลกอริทึมที่ดีมีประสิทธิภาพจำนวนมากก็จะมีลักษณะดังกล่าวนี้ คือ โดยทั่วไปแล้วการอ่านค่าข้อมูลมักจะเป็นคอขวดของการแก้ปัญหา แต่เมื่ออ่านข้อมูลแล้วเสร็จแล้วก็จะทำงานแก้ปัญหาได้อย่างรวดเร็ว ซึ่งอัลกอริทึมที่ไม่มีประสิทธิภาพไม่สามารถทำได้และอีกทั้งยังต้องใช้ทรัพยากรของเครื่องคอมพิวเตอร์มาก

รูปที่ 2.4 แสดงให้เห็นอัตราการเพิ่มของ running time ของอัลกอริทึมทั้ง 4 ซึ่งแสดงให้เห็นว่าอัลกอริทึมที่ไม่มีประสิทธิภาพนั้นใช้งานไม่ได้เลยถึงแม้ว่าขนาดของอินพุตจะมีปริมาณไม่มากนักก็ตาม

มีหลายหนทางในการประมาณการค่า running time ของโปรแกรม ค่าในตารางที่ 2.3 นั้นได้จากการทดลองรันโปรแกรม ถ้าสงสัยว่าโปรแกรม 2 โปรแกรมจะมีการใช้เวลาที่ใกล้เคียงกันแล้วละก็ การที่จะรู้ว่าตัวไหนดีกว่ากันนั้น หนทางที่ดีที่สุดคือการเขียนโปรแกรมและทดสอบรันมันจริง ๆ

โดยทั่วไปแล้ว การแก้ปัญหาหนึ่งจะมีหลาย ๆ อัลกอริทึมด้วยกัน และเราต้องทำการวิเคราะห์อัลกอริทึมก็เพื่อขจัดอัลกอริทึมที่ไม่ดีออกไปตั้งแต่ต้น ยิ่งไปกว่านั้น การวิเคราะห์อัลกอริทึมจะทำให้เห็นประสิทธิภาพของอัลกอริทึมได้ชัดเจนขึ้น และยังทำให้สามารถเห็นจุดที่เป็นคอขวดของวิธีการแก้ปัญหาซึ่งทำให้ระมัดระวังในการเขียนโปรแกรมในจุดคอขวดต่าง ๆ ได้ เพื่อให้ง่ายแก่การวิเคราะห์ เราจะไม่มีการระบุหน่วยของเวลาใด ๆ ดังนั้น เราจะไม่นำค่าคงที่ที่อยู่โดด ๆ มาใช้ และจะไม่นำค่าของเทอมที่มี order ต่ำมาใช้ซึ่งความจริงก็คือการคำนวณ Big-Oh running time นั่นเอง เนื่องจาก Big-Oh เป็นขอบเขตด้านบน (upper bound) นั่นหมายความว่า คำตอบที่ได้จะประกันได้ว่าการทำงานของโปรแกรมนั้น ๆ จะเสร็จสิ้นการทำงานภายในเวลาที่แน่นอนก่อนแน่นอน

ส่วนของโปรแกรมข้างล่างใช้ในการคำนวณหาค่า $∑_{i=1}^Ni^3$

public static int sum( int n )
{
            int partialsum;
/*1*/       partialsum = 0;
/*2*/       for ( int i = 1; i <= n; i++ )
/*3*/            partialsum += i * i * i;
/*4*/       return (partialsum);
}

• การประกาศตัวแปรไม่นับเวลา บรรทัด 1 และ 4 นับเป็นหนึ่งหน่วยเวลาต่อบรรทัด
• บรรทัด 3 นับเป็น 4 หน่วยเวลาต่อการทำงานหนึ่งครั้ง (การคูณ 2 ครั้ง บวก 1 ครั้ง และ assignment อีก 1 ครั้ง) และบรรทัดนี้มีการทำงานทั้งสิ้น $n$ ครั้ง, รวมเป็น $4n$ หน่วยเวลา
• บรรทัดที่ 2 ใช้เวลา initialize ตัวแปร i, ทดสอบเงื่อนไข i ⇐ n, และการเพิ่มค่า i ดังนั้นรวมเวลา คือ 1 หน่วยเวลาสำหรับการ initialize, $n + 1$ หน่วยเวลาสำหรับการทดสอบเงื่อนไข และ $n$ หน่วยเวลาสำหรับการเพิ่มค่า รวมเวลาเท่ากับ $2n + 2$ หน่วยเวลา

ถ้าไม่สนใจเวลาที่ใช้ในการเรียกใช้ฟังก์ชันและเวลาในการส่งค่ากลับแล้ว อัลกอริทึมนี้ก็จะใช้ running time เป็น $6n + 4$ หน่วยเวลา

ดังนั้นเรากล่าวว่าอัลกอริทึมนี้มี running time เป็น $O(n)$ (หมายเหตุ การคำนวณ ผลรวม อนุกรมยกกำลัง 3 สามารถ ใช้สูตร คำนวณได้ โดยไม่ต้อง วนลูบ ทำงานเป็น O(1) )

หากจะต้องทำการวิเคราะห์ดังที่กล่าวมาแล้วนั้นทุกครั้งก็จะเป็นไปไม่ได้ โชคดีที่เราใช้ Big-Oh ทำให้เราสามารถใช้วิธีลัดโดยยังคงได้คำตอบสุดท้ายเช่นเดิม เช่นจากตัวอย่าง บรรทัด 3 เป็นคำสั่งที่เป็น $O(1)$ (ต่อการทำงานหนึ่งครั้ง), ดังนั้นจึงไม่จำเป็นต้องนับหน่วยเวลาว่าจะมีค่าเป็น 1 หรือ 2 หรือเท่าใดก็ไม่จำเป็น บรรทัด 1 ใช้หน่วยเวลาที่น้อยมากจนไม่มีความสำคัญเมื่อเทียบกับหน่วยเวลาที่ต้องใช้ทำงานการวนรอบ (for loop), ดังนั้นจึงไม่มีความจำเป็นต้องใส่ใจมัน จากที่กล่าวมานี้นำมาซึ่งกฎเกณฑ์ทั่วไปที่จะใช้ต่อไป

RULE 1-FOR LOOPS:

Running time ของ for loop หนึ่ง มีค่ามากที่สุดเท่ากับ running time ของคำสั่งภายในลูป (รวมคำสั่งทดสอบเงื่อนไขด้วย) คูณด้วยจำนวนครั้งของการวนรอบลูป

RULE 2-NESTED FOR LOOPS:

จะต้องทำการวิเคราะห์จากภายในลูปออกมาภายนอก และ Running time รวมทั้งสิ้นของกลุ่มคำสั่งในลูปซ้อน คือ running time ของคำสั่งคูณด้วยผลคูณของขนาดของ for loops ทั้งหมด เช่นส่วนของโปรแกรมต่อไปนี้มี running time เป็น $O(n^2)$:

for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		k++; 

RULE 3-CONSECUTIVE STATEMENTS:

รวม running time ของแต่ละส่วนเข้าด้วยกัน (ซึ่งหมายความว่าจะได้ผลลัพธ์เป็นค่าของตัวที่มากที่สุดนั่นเอง ดูกฎที่ 1(a) หน้าที่ 2)

ส่วนโปรแกรมต่อไปนี้มี running time $O(n)$ ตามด้วย $O(n^2)$ ดังนั้น ทั้งหมดจึงมี running time $O(n^2)$

for ( i = 0; i < n; i++)
       a[i] = 0;
for ( i = 0; i < n; i++ )
       for ( j = 0; j < n; j++ )
              a[i] += a[j] + i + j;

RULE 4-lF/ELSE:

สำหรับ

if( cond )
	S1
else
	S2

Running time ของคำสั่ง if/else หนึ่งจะไม่มากไปกว่า running time ของ การทดสอบเงื่อนไขบวกกับ running time ที่มากกว่าระหว่าง running time ของ S1 กับ S2

โดยพื้นฐานแล้ววิธีที่ใช้ในการวิเคราะห์ คือ ให้ทำการวิเคราะห์จากส่วนที่อยู่ภายในที่สุดของกลุ่มคำสั่งออกมา ถ้าเป็นกรณีที่มีการเรียกใช้ routine ก็ให้ทำการวิเคราะห์ routine นั้น ๆ ก่อน

กรณีเป็น recursive procedures มีทางเลือกในการวิเคราะห์หลายทาง เช่นถ้า recursion นั้นเป็น routine ที่สามารถใช้ for loop แทนได้ก็ให้ใช้วิธีที่กล่าวมาแล้ว ดังเช่น ฟังก์ชันข้างล่างนี้สามารถแทนได้ด้วย loop ง่าย ๆ ดังนั้นมันจึงมี running time เป็น $O(n)$:

public static long factorial ( int n )
{
	if ( n <= 1 )
	    return 1;
	else
	    return ( n * factorial(n-1) );
}

นี่เป็นตัวอย่างที่ไม่ดีของการใช้ recursion เมื่อไรก็ตามที่มีการใช้ recursion อย่างเหมาะสมก็จะเป็นการยากที่จะเปลี่ยนมันให้เป็นแบบลูปอย่างง่ายได้

ในกรณีเช่นนี้โดยทั่วไปแล้วการวิเคราะห์ recursion จะเกี่ยวข้องกับ recurrence relation ซึ่งต้องทำการหา solution ตัวอย่างต่อไปนี้เป็นตัวอย่างที่เลวร้ายมากในการใช้ recursion

public static long fib( int n )
{
/*1*/       if ( n <= 1 )
/*2*/           return 1;
       		else
/*3*/           return ( fib(n-1) + fib(n-2) );
}

การใช้ recursion แบบนี้ดูเหมือนเป็นวิธีที่ดี อย่างไรก็ตามถ้าทำการรันโปรแกรมนี้ที่มี n ประมาณ 40 ก็จะเห็นความไร้ประสิทธิภาพของโปรแกรม

การวิเคราะห์ running time ไม่ได้ยุ่งยากแต่อย่างใด

โดยเริ่มต้นกำหนดให้ $T(n)$ เป็น running time ของฟังก์ชัน $fib(n)$ ถ้า $n = 0$ หรือ $n = 1$, running time คือค่าคงที่ค่าหนึ่ง ซึ่งก็คือเวลาที่ใช้ในการทดสอบเงื่อนไขในบรรทัดที่ 1 และเวลาที่ใช้ในการ return ค่า ดังนั้น จึงกล่าวว่า $T(0) = T(1) = 1$ ได้เนื่องจากค่าคงที่ไม่มีความหมายที่สำคัญ

ค่า running time สำหรับค่าอื่น ๆ ของ $n$ จึงหาได้จากการเทียบกับ running time ของ base case สำหรับ $n > 2$, เวลาที่ใช้ในการทำงานของฟังก์ชันคือ ค่าคงที่ในบรรทัด 1 บวกกับเวลาทำงานในบรรทัด 3 การทำงานของบรรทัด 3 ประกอบด้วยการบวกหนึ่งครั้งและเรียกใช้ฟังก์ชัน 2 ครั้ง เนื่องการเป็นการเรียกใช้ฟังก์ชัน ดังนั้นจึงต้องทำการวิเคราะห์ฟังก์ชันที่ถูกเรียกนั้นเสียก่อน ฟังก์ชันที่เรียกใช้ครั้งแรกคือ $fib(n - 1)$ และดังนั้นด้วยนิยามของ T, การเรียกใช้นี้จึงใช้เวลา $T(n - 1)$ หน่วยเวลา และในทำนองเดียวกัน การเรียกใช้อีกครั้งหนึ่งจึงใช้เวลา $T(n - 2)$ หน่วยเวลา ดังนั้นเวลาทั้งหมดที่ต้องใช้ คือ $ T(n - 1) + T(n - 2) + 2, $ เมื่อ 2 คือค่าเวลาที่ใช้ในบรรทัดที่ 1 บวกด้วยเวลาการบวกในบรรทัดที่ 3 ดังนั้น สำหรับ $n > 2$, จะได้สมการของ running time ของฟังก์ชัน $fib(n)$ เป็น: $$T(n) = T(n - 1) + T(n - 2) + 2 $$ เนื่องจาก $fib(n) = fib(n-1) + fib(n-2)$ เราสามารถแสดงให้เห็นได้ว่า $T(n) ≥ fib(n)$ ได้ induction prove และสามารถแสดงให้เห็นได้ว่า $fib(n) ≥ (3/2)^n$ (ดูตัวอย่างที่ 1 หัวข้อที่ 1.2.5 ในบทที่ 1) ดังนั้นฟังก์ชันนี้จึงมีการเติบโตแบบ exponential โดยที่จริงแล้วถ้าเพียงแต่ใช้ for-loop ก็จะสามารถลด running time ลงได้อย่างมาก

ฟังก์ชันนี้ทำงานได้ช้ามากก็เนื่องจากว่ามันทำงานที่ไม่จำเป็นต้องทำเป็นจำนวนมาก โดยจะเห็นได้ในบรรทัดที่ 3 ที่เป็นการคำนวณ $f(n-1)$ นั้นความจริงได้ทำการคำนวณค่า $f(n-2)$ ไว้แล้วด้วย แต่ถูกละทิ้งไปเสียและต้องทำการคำนวณค่านี้ใหม่ในการเรียกใช้ฟังก์ชันบรรทัดที่ 3 ในครั้งที่ 2 การทิ้งค่าที่คำนวณแล้วและจะต้องใช้เวลาคำนวณค่าเดิมใหม่นี้ก็อยู่ในรูป recursion เช่นกันซึ่งหมายความว่าต้องใช้ running time ในปริมาณสูงมาก

ในหัวข้อนี้จะได้แสดงอัลกอริทึมทั้ง 4 ที่ใช้ในการแก้ปัญหา maximum subsequence sum ที่ได้กล่าวมาก่อนหน้านี้ อัลกอริทึมที่ 1 แสดงไว้ในรูปที่ 2.5

public static int maxSubSum1( int [ ] a )
{
/* 1*/      int maxSum = 0;
/* 2*/      for( int i = 0; i < a.length; i++ )
/* 3*/          for( int j = i; j < a.length; j++ )
                  {
/* 4*/              int thisSum = 0;
/* 5*/              for( int k = i; k <= j; k++ )
/* 6*/                  thisSum += a[ k ];
/* 7*/              if( thisSum > maxSum )
/* 8*/                  maxSum   = thisSum;
                  }
/* 9*/      return maxSum;
 }

รูปที่ 2.5 แสดงอัลกอริทึมที่ 1

ในโปรแกรมไม่ได้มีการคำนวณตัว subsequence ที่ใช้และถ้าต้องการก็จะต้องเขียนคำสั่งเพิ่มเติม ฟังก์ชันนี้มี running time เป็น $O(n^3)$ และเหตุผลก็มาจากการทำงานในบรรทัดที่ 5 และ 6 ซึ่งประกอบด้วยการทำงานที่เป็น $O(1)$ ฝังอยู่ภายใน 3 ลูปที่ซ้อนกันของคำสั่ง for และลูปที่บรรทัดที่ 2 มีขนาดเป็น $n$

ลูปที่สองมีขนาดเป็น $n – i$ ซึ่งอาจจะมีขนาดเล็กแต่ก็สามารถมีขนาดเท่ากับ n ได้เช่นกัน และเราจะต้องประมาณการให้เป็นค่าที่เลวร้ายที่สุด (worst case)

ลูปที่สามมีขนาดเป็น j – i + 1 ซึ่งเช่นเดียวกันที่เราจะต้องประมาณการให้มันมีขนาด n ได้ รวมเวลาทั้งสิ้นแล้วจึงเท่ากับ $O(1 · n · n · n) = O(n^3)$ บรรทัดที่ 6 ใช้เวลารวม O(1) เท่านั้น และบรรทัด 7 และ 8 ใช้เวลา $O(n^2)$ เนื่องจากมันเป็นนิพจน์ง่าย ๆ ที่อยู่ในลูปซ้อน

ถ้าทำการวิเคราะห์ให้ละเอียดแม่นยำขึ้นด้วยการใช้ขนาดจริงของลูปเหล่านั้นก็จะได้คำตอบเป็น $\Theta(n^3)$ การวิเคราะห์นี้ได้จากการหาผลบวกของ $∑_{i=0}^{n-1}∑_{j=i}^{n-1}∑_{k=i}^j1$, ซึ่งเป็นค่าของจำนวนครั้งของการทำงานของบรรทัดที่ 6 และหาค่าได้ดังนี้

เริ่มต้นเรามี $$∑_{k=i}^j 1 = j - i + 1$$ จากนั้นเป็นการหาค่าของถัดมา คือ $$ ∑_{j=i}^{n-1} (j-i+1) = \frac{(n-i + 1)(n-i)}{2} $$ สุดท้ายหาค่า \begin{align*} ∑_{i=0}^{n-1} \frac{(n-i+1)(n-i)}{2} & =∑_{i=1}^n \frac{(n-i+1)(n-i+2)}{2} \\ & = \frac{1}{2} ∑_{i=1}^n i^2 - (\frac{n+3}{2}) ∑_{i=1}^n \frac{i+1}{2} (n^2+3n+2) ∑_{i=1}^n 1 \\ & = \frac{1}{2} \frac{n(n+1)(2n+1)}{6} - (\frac{n+3}{2}) \frac{n(n+1)}{2} + \frac{(n^2+3n+2)}{2} n \\ & =\frac{(n^3+3n^2+2n)}{6} \end{align*}

เราจะสามารถหลีกเลี่ยง running time ที่เป็น cubic ด้วยการเอาลูปของ for ออก การคำนวณในบรรทัดที่ 5 และ 6 ในอัลกอริทึม 1 เป็นการทำงานที่สิ้นเปลือง รูปที่ 2.6 เป็นอัลกอริทึม 2 ที่มี running time เป็น $O(n^2)$

public static int maxSubSum2( int [ ] a )
 {
/* 1*/      int maxSum = 0;
/* 2*/      for( int i = 0; i < a.length; i++ )
            {
/* 3*/          int thisSum = 0;
/* 4*/          for( int j = i; j < a.length; j++ )
                {
/* 5*/              thisSum += a[ j ];
/* 6*/              if( thisSum > maxSum )
/* 7*/                  maxSum = thisSum;
                }
            }
/* 8*/      return maxSum;
 }

รูปที่ 2.6 แสดงอัลกอริทึมที่ 2

ยังมีอัลกอริทึมในการแก้ปัญหานี้ที่เป็นแบบ recursive ที่มี running time เป็น $O(n\ log\ n)$ และเป็นตัวอย่างที่ดีของการใช้อัลกอริทึมแบบ recursive อัลกอริทึมที่ 3 นี้เป็นการทำงานแก้ปัญหาในรูปแบบที่เรียกว่า divide-and-conquer แนวคิดก็คือการแบ่งปัญหาออกเป็นปัญหาย่อย 2 ปัญหาที่มีขนาดโดยประมาณเท่า ๆ กัน แล้วทำการแก้ปัญหาย่อยนั้นในแบบ recursive การทำงานขั้นตอนนี้เรียกว่า “divide” จากนั้นจึงนำคำตอบของแต่ละปัญหาย่อยนั้นมารวมเข้าด้วยกัน ซึ่งเป็นขั้นตอนที่เรียกว่า “conquer”

ในกรณีของเรานั้น ค่า maximum subsequence sum อาจเกิดขึ้นได้ในพื้นที่ใดพื้นที่หนึ่งจากสามพื้นที่ด้วยกันคือ ทั้งหมดเกิดขึ้นจากค่าทั้งหมดที่อยู่ในพื้นที่ด้านครึ่งซ้าย หรือ จากค่าทั้งหมดที่อยู่ในพื้นที่ด้านครึ่งขวา หรือ เกิดจากค่าที่อยู่คร่อมทั้งสองข้าง และถ้าเป็นสองกรณีแรกเราก็สามารถหาคำตอบแบบ recursive ได้

ส่วนกรณีที่สามได้จากการหาผลบวกที่มากที่สุดในครึ่งแรกที่รวมสมาชิกตัวสุดท้ายในครึ่งแรกและผลบวกที่สามที่สุดในครึ่งหลังที่รวมสมาชิกตัวแรกของครึ่งหลังอยู่ด้วยแล้วนำมารวมกัน พิจารณาอินพุตต่อไปนี้:

Maximum subsequence sum ของครึ่งแรกคือ 6 (จาก a1 ถึง a3), และของครึ่งหลังคือ 8 (จาก a6 ถึง a7)

Maximum sum ของครึ่งแรกที่รวมตัวสุดท้ายของครึ่งแรกไว้ด้วยคือ 4 (จาก a1 ถึง a4), และ maximum sum ในครึ่งหลังที่รวมตัวแรกของครึ่งหลังไว้ด้วยคือ 7 (จาก a5 ถึง a7) ดังนั้น maximum sum ที่คร่อมทั้งสองส่วนโดยรวมตัวกลางไว้ด้วย คือ 4 + 7 = 11 (จาก a1 ถึง a7) ดังนั้นคำตอบของปัญหานี้ คือ 11 รูปที่ 2.7 แสดงอัลกอริทึม (โปรแกรม) ที่ 3 ที่กล่าวมานี้

รูปแบบทั่วไปของ recursive call คือการส่งผ่าน input array พร้อมด้วยค่าขอขอบเขตซ้ายและขอบเขตขวาที่เป็นตัวกำหนดส่วนของอะเรย์ที่จะมีการทำงานเกิดขึ้น ส่วนของโปรแกรมที่ใช้เป็น driver เริ่มต้นส่งผ่านค่าของขอบเขตด้วย 0 และ n – 1 พร้อมกับตัวอะเรย์

private static int maxSumRec( int [ ] a, int left, int right )
{
/* 1*/      if( left == right )  // Base case
/* 2*/          if( a[ left ] > 0 )
/* 3*/              return a[ left ];
                  else
/* 4*/              return 0;
/* 5*/      int center = ( left + right ) / 2;
/* 6*/      int maxLeftSum  = maxSumRec( a, left, center );
/* 7*/      int maxRightSum = maxSumRec( a, center + 1, right );
/* 8*/      int maxLeftBorderSum = 0, leftBorderSum = 0;
/* 9*/      for( int i = center; i >= left; i-- )
            {
/*10*/          leftBorderSum += a[ i ];
/*11*/          if( leftBorderSum > maxLeftBorderSum )
/*12*/              maxLeftBorderSum = leftBorderSum;
            }
/*13*/      int maxRightBorderSum = 0, rightBorderSum = 0;
/*14*/      for( int i = center + 1; i <= right; i++ )
              {
/*15*/          rightBorderSum += a[ i ];
/*16*/          if( rightBorderSum > maxRightBorderSum )
/*17*/              maxRightBorderSum = rightBorderSum;
              }
/*18*/      return max3( maxLeftSum, maxRightSum,
/*19*/                   maxLeftBorderSum + maxRightBorderSum );
 }
 
 /** Driver for divide-and-conquer maximum contiguous subsequence sum algorithm. */
 public static int maxSubSum3( int [ ] a )
 {
        return maxSumRec( a, 0, a.length - 1 );
 }
 
/** Return maximum of three integers.    */
private static int max3( int a, int b, int c )
{
         return a > b ? a > c ? a : c : b > c ? b : c;
} 

รูปที่ 2.7 แสดงอัลกอริทึมที่ 3

บรรทัดที่ 1 ถึง 4 เป็นส่วนจัดการ base case กล่าวคือ ถ้า left = right นั่นคือมีสมาชิกเพียง 1 ตัว และมันก็จะเป็นค่า maximum subsequence sum ถ้ามันไม่เป็นค่าลบ

บรรทัดที่ 6 และ 7 เป็น recursive call จะเห็นว่าโดยปกติแล้ว recursive call จะเกิดกับขนาดของปัญหาที่เล็กลงกว่าเดิม

บรรทัดที่ 8 ถึง 12 และบรรทัดที่ 13 ถึง 17 คำนวณค่า maximum sum 2 ค่าที่รวมค่าที่เป็นค่าแบ่งครึ่ง 2 ด้าน และผลบวกของค่าทั้ง 2 นี้ก็จะเป็นค่า maximum sum ที่ครอบคลุมทั้งครึ่งแรกและครึ่งหลัง (คือครอบคลุมทั้งสองครึ่ง)

ฟังก์ชัน max3 จะให้ค่ากลับเป็นค่ามากที่สุดของ 3 ค่าดังกล่าวนี้

จะเห็นได้ว่าอัลกอริทึม 3 ดูจะโปรแกรมยุ่งยากกว่า 2 อัลกอริทึมแรก อย่างไรก็ตามโปรแกรมที่มีขนาดเล็กกว่าไม่ได้หมายความว่าจะเป็นโปรแกรมที่ดีกว่าเสมอไป การวิเคราะห์หา running time ก็เป็นเช่นเดียวกับที่ใช้ในการวิเคราะห์ running time ของโปรแกรมคำนวณหา Fibonacci number คือ

ให้ T(n) เป็นเวลาที่ใช้ในการหา maximum subsequence sum ที่มีสมาชิกจำนวน $n$ ตัว กรณีถ้า $n = 1$ โปรแกรมจะใช้จำนวนเวลาคงที่ในการทำงานบรรทัดที่ 1 ถึง 4 ซึ่งเราใช้เป็นหนึ่งหน่วยเวลา ดังนั้น $T(1) = 1$

ถ้ามิฉะนั้น โปรแกรมก็จะทำงาน recursive call 2 ครั้ง และการทำงาน for-loop 2 ลูป ระหว่างบรรทัดที่ 9 ถึงบรรทัดที่ 17 และงานเล็ก ๆ น้อย ๆ ดังเช่นบรรทัดที่ 5 และ 18 การทำงานของ for-loop ทั้ง 2 ลูปจะเป็นการเข้าถึงสมาชิกทุกตัวของ subarray และการทำงานในลูปเป็นเวลาคงที่ ดังนั้นเวลาที่ใช้ทั้งสิ้นระหว่างบรรทัดที่ 9 ถึง 17 คือ O(n) คำสั่งบรรทัดที่ 1 ถึง 5, 8, 13, และ 18 ล้วนใช้เวลาคงที่และสามารถละเลยได้เมื่อเทียบกับ O(n) ส่วนที่เหลือคือบรรทัดที่ 6 และ 7 เป็นการหา maximum subsequence sum ของขนาดข้อมูลเป็น $n/2$ (สมมติ n เป็นเลขคู่) ดังนั้นบรรทัดทั้งสองนี้จะใช้เวลา $T(n/2)$ หน่วยเวลา รวมเป็น $2T(n/2)$ รวมเวลาทั้งสิ้นของอัลกอริทึมคือ $2T(n/2) + O(n)$ ดังนั้นจะได้สมการ $$T(1) = 1$$ $$T(n) = 2T(n/2) + O(n)$$

เพื่อให้ง่ายแก่การคำนวณเราสามารถแทนเทอมของ $O(n)$ ด้วย $n$ ได้โดยไม่มีผลต่อคำตอบทั้งนี้เนื่องจากเราต้องการผลในรูปของ Big-O อยู่แล้ว ถ้าให้ $n=2^k$ และหาผลลัพธ์ของ recurrence relation จะได้คำตอบ $T(n) = n\ log\ ⁡n + n = O(n\ log⁡\ n)$

อัลกอริทึมที่ 4 เพื่อหาค่า maximum subsequence sum แสดงไว้ในรูปที่ 2.8 จากอัลกอริทึมที่ 1 และ 2 จะเห็นได้ว่า i เป็นตัวกำหนดตำแหน่งเริ่มต้นของ sequence ในขณะหนึ่ง ๆ และ j เป็นตัวกำหนดตำแหน่งสุดท้ายของ sequence ในขณะนั้น ๆ ในกรณีที่เราไม่ต้องการรู้ว่าค่าสูงสุดของผลบวกที่ได้นั้นเกิดใน subsequence ใด เราก็สามารถปรับปรุงอัลกอริทึม 2 ได้ โดยเราจะเห็นได้ว่า

ถ้า a[i] เป็นค่าติดลบก็หมายความว่ามันก็ไม่น่าจะใช้เป็นค่าแรกของ sequence ที่ดีได้เพราะเหตุว่า subsequence ที่เริ่มต้นด้วย a[i+1] น่าจะดีกว่า เริ่ม subsequence ที่เริ่มต้นด้วย a[i] และในทำนองเดียวกัน subsequence ใด ๆ ที่มีค่ารวมเป็นค่าติดลบมันก็ไม่น่าจะเป็น subsequence ที่อยู่หน้า subsequence ที่ต่อเนื่องมาได้ดี

นั่นคือถ้าเราตรวจพบว่า inner loop ของอัลกอริทึม 2 ทำให้เกิดค่าของ subsequence จาก a[i] ถึง a[j] เป็นค่าติดลบ เราก็จะเลื่อนค่า i ขึ้นจนกระทั่งถึง j+1 การที่เราทำเช่นนี้ได้ก็เนื่องจากว่าเราจะเห็นว่าถ้าเราให้ p เป็นตำแหน่ง index ใด ๆ ที่อยู่ระหว่าง i + 1 ถึง j แล้วก็หมายความว่า subsequence ใด ๆ ที่เริ่มต้นด้วย index หมายเลข p ก็จะไม่สามารถมีค่ามากกว่าค่า subsequence ที่เริ่มต้นด้วย index i และรวม subsequence ที่เริ่มต้นด้วย a[i] ถึง a[p – 1] เนื่องจาก subsequence นี้ (คือจาก a[i] ถึง a[p – 1] ) ไม่เป็นค่าติดลบ (และ j เป็นค่า index ตัวแรกที่ทำให้ subsequence ที่เริ่มต้นด้วย index i กลายเป็นค่าติดลบ) ดังนั้นเราจึงสามารถเลื่อนค่าของ index i ขึ้นไปจนถึงค่า j + 1 ได้โดยไม่ผิด

/** Linear-time maximum contiguous subsequence sum algorithm.   */
        public static int maxSubSum4( int [ ] a )
        {
/* 1*/      int maxSum = 0, thisSum = 0;
/* 2*/      for( int j = 0; j < a.length; j++ )
            {
/* 3*/          thisSum += a[ j ];
/* 4*/          if( thisSum > maxSum )
/* 5*/              maxSum = thisSum;
/* 6*/          else if( thisSum < 0 )
/* 7*/              thisSum = 0;
            }
/* 8*/      return maxSum;
        }

รูปที่ 2.8 แสดงอัลกอริทึมที่ 4 ของการหา maximum subsequence sum

ข้อดีที่ได้เพิ่มขึ้นมาของอัลกอริทึมนี้คือมันอ่านค่าหน่วยข้อมูลเพียงรอบเดียว และเมื่อมีการอ่านค่าและประมวลผลค่า a[i] แล้วก็ไม่จำเป็นต้องเก็บหรือจดจำค่านี้ในหน่วยความจำอีก นอกจากนั้น ในระหว่างการทำงาน ณ เวลาใด ๆ ของอัลกอริทึม มันยังสามารถให้คำตอบของปัญหา subsequence sum ของหน่วยข้อมูลชุดที่มันได้อ่านค่าไปแล้วด้วย (ซึ่งอัลกอริทึมอื่นทำไม่ได้) อัลกอริทึมที่สามารถทำแบบนี้ได้เรียกว่า on-line algorithms อัลกอริทึมที่ต้องการใช้เนื้อที่ที่คงที่และใช้เวลารันเป็น linear time

ความสับสนในการวิเคราะห์อัลกอริทึมมักจะเกิดขึ้นเสมอเมื่อปัญหานั้นเกี่ยวข้องกับ logarithm เราได้เห็นอัลกอริทึมแบบ divide-and-conquer ที่มี running time เป็น $O(n\ log\ n)$ มาแล้ว นอกจาก อัลกอริทึมแบบ divide-and-conquer แล้วยังมีอัลกอริทึมอื่น ๆ อีกที่เป็น logarithm ซึ่งโดยทั่วไปแล้วเกิดขึ้นเมื่ออัลกอริทึ่มนั้น ๆ เป็นดังนี้

อัลกอริทึมจะมี running time เป็น $O(log\ n)$ ถ้ามันใช้เวลาคงที่ $O(1)$ เพื่อที่จะลดขนาดของปัญหาลงเป็นสัดส่วนที่แน่นอนหนึ่ง (ซึ่งปกติจะเป็น 1/2) ในอีกด้านหนึ่ง ถ้าอัลกอริทึมต้องใช้เวลาที่คงที่ในการลดขนาดของปัญหาลงเป็นจำนวนที่คงที่หนึ่ง (เช่นลดขนาดของปัญหาลงได้ทีละ 1), อัลกอริทึมนั้นก็จะเป็น $O(n)$

กรณีที่อินพุตมีขนาด n ตัว อัลกอริทึมจะต้องใช้เวลาในการอ่านอินพุตนี้เป็นเวลา $O(n)$ ดังนั้น เมื่อเรากล่าวว่าปัญหาหนึ่งแก้ได้ด้วยอัลกอริทึมที่มี running time เป็น $O(log\ n)$ เราหมายความว่าอินพุตได้รับการอ่านค่ามาเรียบร้อยแล้ว ต่อไปจะเป็นตัวอย่างของอัลกอริทึมที่มีลักษณะดังกล่าวนี้มาแล้ว 3 อัลกอริทึม

Binary search

กำหนดให้ x เป็นเลขจำนวนเต็มและชุดเลขจำนวนเต็ม $a_0, a_1, a_2, . . . , a_n$, ที่มีการจัดเรียงแล้วอยู่ในหน่วยความจำ, ให้หาค่า i ที่ $a_i$ = x, หรือให้ i = -1 ถ้า x ไม่เท่ากับค่า a ใด ๆ

วิธีการที่ชัดเจนคืออ่านค่าในรายการเรียงลำดับจากซ้ายไปขวาซึ่งจะใช้เวลาเป็น linear time อย่างไรก็ตามอัลกอริทึมนี้ไม่ได้ใช้ประโยชน์จากข้อเท็จจริงที่ว่ารายการข้อมูลนี้มีการจัดเรียงไว้เรียบร้อยแล้ว

กรรมวิธีที่ดีกว่านี้ก็คือตรวจดูว่าค่า x ที่ต้องการนั้นอยู่ที่ตำแหน่งตรงกลางหรือไม่

ถ้าใช่เราก็จะได้คำตอบทันที ถ้าค่า x ที่ต้องการนั้นมีค่าน้อยกว่าค่าตรงกลาง

เราก็สามารถใช้วิธีการเดิมที่ได้กล่าวมานี้กับอะเรย์ย่อย (ซึ่งเป็นอะเรย์ที่จัดเรียงอยู่แล้ว) ที่อยู่ทางด้ายซ้ายของสมาชิกตัวกลาง หรือถ้าค่า x ที่ต้องการนั้นมีค่ามากกว่าค่าตรงกลาง

เราก็สามารถใช้วิธีการเดิมนี้กับอะเรย์ย่อย (ซึ่งเป็นอะเรย์ที่จัดเรียงอยู่แล้ว) ที่อยู่ทางด้ายขวาของสมาชิกตัวกลาง รูปที่ 2.9 แสดงฟังก์ชัน binary search จากฟังก์ชัน binary search ในรูปที่ 2.9 เห็นได้ว่าการทำงานทั้งหมดที่เกิดขึ้นภายในลูปใช้เวลาเป็น $O(1)$ ต่อการทำงานหนึ่งรอบ ดังนั้นการวิเคราะห์เป็นเพียงการจำนวนรอบของการวนในลูปเท่านั้น โดยที่ลูปเริ่มต้นด้วยค่า high – low = n – 1 และจบลงด้วยค่า high – low ≥ - 1 แต่ละรอบของการทำงานในลูปจะทำให้ค่า low – high ลดลงครึ่งหนึ่งเป็นอย่างน้อยจากค่าเดิมก่อนหน้า

ดังนั้นจำนวนครั้งที่มากที่สุดของการทำงานวนรอบลูปคือ ⌈ $log⁡(n-1)$ ⌉+2 (เช่นถ้า high – low = 128 นั่นคือ ค่าที่มากที่สุดของ high – low หลังการทำงานแต่ละรอบการทำงาน คือ 64, 32, 16, 8, 4, 2, 1, 0, -1,) ดังนั้น running time จึงเป็น $O(log\ n)$ และเช่นเดียวกัน เราสามารถเขียนสมการของ running time ในรูปแบบ recursive เช่นกัน เพียงแต่ถ้าเราวิเคราะห์ได้ว่าเกิดอะไรขึ้นในอัลกอริทึม เราก็ไม่จำเป็นต้องวิเคราะห์ผ่านทางสมการ recursive binary search ดูจะเป็นโครงสร้างข้อมูลแรกที่กล่าวถึงของเรา มันมี running time ของการทำงานการค้นหา (find) เป็น $O(log\ n)$ แต่การทำงานอื่น ๆ (เช่น insert) มี running time เป็น $O(n)$ ซึ่งมีประโยชน์มากในกรณีที่ข้อมูลเป็นแบบ static (คือไม่มี delete หรือ insert)

/* 	Performs the standard binary search.
	@return index where item is found, or -1 if not found  */
        public static int binarySearch( Comparable [ ] a, Comparable x )
        {
/* 1*/      int low = 0, high = a.length - 1;
/* 2*/      while( low <= high )
            {
/* 3*/          int mid = ( low + high ) / 2;
/* 4*/          if( a[ mid ].compareTo( x ) < 0 )
/* 5*/              low = mid + 1;
/* 6*/          else if( a[ mid ].compareTo( x ) > 0 )
/* 7*/              high = mid - 1;
                else
/* 8*/              return mid;   		// Found
            }
/* 9*/      return NOT_FOUND;     	// NOT_FOUND is defined as -1
        } 

รูปที่ 2.9 ฟังก์ชัน binary search

Euclid's Algorithm

ตัวอย่างที่ 2 ที่จะกล่าวถึงคือ อัลกอริทึมของการคำนวณหาค่าตัวหารร่วมมากของ Euclid ค่าของตัวหารร่วมมาก (ห.ร.ม. หรือ greatest common divisor, gcd) ของเลขจำนวนเต็ม 2 ตัว คือค่าเลขจำนวนเต็มที่มีค่ามากที่สุดที่ยังหารตัวเลข 2 ตัวแรกได้ลงตัว เช่น gcd(50, 15) = 5

รูปที่ 2.10 แสดงอัลกอริทึมในการคำนวณ gcd(m, n) โดยที่ m ≥ n (ถ้าหาก n > m การทำงานในรอบแรกก็จะเป็นการสลับค่ากัน) อัลกอริทึมจะทำการคำนวณค่าเศษที่เหลือจากการหารไปเรื่อย ๆ จนกระทั่งค่าเศษที่ได้เป็น 0 และค่าเศษที่เหลือตัวสุดท้ายที่ไม่เท่ากับ 0 จะเป็นคำตอบ

เช่นถ้า m = 1989 และ n = 1590 ก็จะได้ค่าของเศษตามลำดับคือ 399, 393, 6, 3, 0 ดังนั้น gcd(1989, 1590) = 3

การประมาณการ running time จะขึ้นอยู่กับการหาจำนวนของ sequence ของเศษที่เหลือจากการหาร ถึงแม้ว่าค่าของเศษที่ได้จากการหารแต่ละรอบการทำงานจะไม่ได้ลดลงในสัดส่วนที่คงที่หนึ่งก็ตาม แต่เราก็สามารถพิสูจน์ได้ว่าภายหลังจากการหารไปแล้ว 2 ครั้ง เศษที่ได้ก็จะมีค่ามากที่สุดได้เท่ากับครึ่งหนึ่งของค่าเดิม ซึ่งจะเป็นการแสดงให้เห็นว่าจำนวนครั้งของการวนรอบมีจำนวนมากที่สุดคือ $2\ log\ n = O(log\ n)$ ซึ่งก็คือ running time

THEOREM 2.1: ถ้า $m > n$, แล้ว $m\ mod\ n < m/2$

PROOF:

แบ่งเป็นสองกรณี คือ ถ้า $n < m/2$, แล้วเห็นได้เลยว่าทฤษฎีเป็นจริง เนื่องจากเศษที่ได้จะน้อยกว่าค่า $n$

กรณีที่ $n > m/2$ แล้ว $n$ จะหาร $m$ ครั้งหนึ่งโดยมีเศษที่ได้คือ $m - n$ ซึ่งจะน้อยกว่า $m/2$, ดังนั้นทฤษฎีเป็นจริง

public static long gcd( long m, long n )
        {
/* 1*/      while( n != 0 )
            {
/* 2*/          long rem = m % n;
/* 3*/          m = n;
/* 4*/          n = rem;
            }
/* 5*/      return m;

รูปที่ 2.10 Euclid's Algorithm ในการคำนวณ gcd(m, n)

Exponentiation

ตัวอย่างนี้เป็นการคำนวณหาค่าของการยกกำลังของเลขจำนวนเต็ม (โดยตัวยกกำลังก็เป็นเลขจำนวนเต็ม) และเราจะสมมุติว่าเครื่องคอมพิวเตอร์สามารถเก็บค่า integers ขนาดใหญ่ ๆ ได้ เราจะใช้การนับจำนวนการคูณเป็นตัววัด running time การคำนวณค่า $x^n$ ด้วยวิธีง่าย ๆ ที่สุดจะต้องใช้จำนวนครั้งของการคูณทั้งสิ้นเท่ากับ n-1 ครั้ง

แต่อัลกอริทึมแบบ recursive ที่แสดงไว้ในรูปที่ 2.11 ทำได้ดีกว่า คำสั่งในบรรทัดที่ 1 ถึง 4 จัดการกับ base case ของฟังก์ชัน ถ้า n เป็นเลขคู่จะได้ว่า $x^n=x^{n⁄2}∙x^{n⁄2}$ และ ถ้า n เป็นเลขคี่จะได้ว่า $x^n=x^{((n-1))⁄2}∙x^{((n-1))⁄2}∙x$

เช่นถ้าต้องการคำนวณค่า $x^{62}$ อัลกอริทึมก็จะทำการคำนวณค่าต่อไปนี้โดยใช้จำนวนครั้งของการคูณกันเพียง 9 ครั้งเท่านั้น $x^3=x^2∙x$, $x^7=(x^3)^2∙x$, $ x^{15}=(x^7)^2∙x$, $x^{31}=(x^{15})^2∙x$, $x^{62}=(x^{31})^2$

จะเห็นว่าต้องใช้จำนวนครั้งของการคูณมากที่สุดเท่ากับ $2\ log\ n$ เนื่องจากจำนวนครั้งสูงสุดของการคูณที่ต้องการเพื่อลดขนาดปัญหาลงครึ่งหนึ่งคือ 2 (ถ้า n เป็นคี่) อย่างไรก็ตามเราสามารถวิเคราะห์อัลกอริทึมจากรูปที่ 2.11 ซึ่งจะได้สมการ recurrence และหา solution เพื่อหาผลลัพธ์เป็นคำตอบได้เช่นเดียวกัน

public static long pow( long x, int n )
{
/* 1*/      if( n == 0 )
/* 2*/          return 1;
/* 3*/      if( n == 1 )
/* 4*/          return x;
/* 5*/      if( isEven( n ) )
/* 6*/          return pow( x * x, n / 2 );
            else
/* 7*/          return pow( x * x, n / 2 ) * x;
}

รูปที่ 2.11 Exponentiation algorithm

หลังจากที่ได้ทำการวิเคราะห์อัลกอริทึมแล้วก็จะเป็นการตรวจสอบดูว่าการวิเคราะห์ของเราถูกต้องมากน้อยแค่ไหน วิธีการที่สามารถใช้ได้วิธีการหนึ่งคือการเขียนโปรแกรมแล้วทดลองรันโปรแกรมเพื่อดูว่า running time ใกล้เคียงกับที่ได้วิเคราะห์หรือไม่

ถ้าเพิ่ค่าของ n ขึ้นสองเท่าแล้วค่าของ running time ก็เพิ่มขึ้นสองเท่าด้วยนั่นหมายความว่า running time เป็น linear time

ถ้า n เพิ่มขึ้นสองเท่าแล้ว running time เพิ่มขึ้นสี่เท่า นั่นหมายความว่า running time เป็น quadratic

ถ้า n เพิ่มขึ้นสองเท่าแล้ว running time เพิ่มขึ้นแปดเท่า นั่นหมายความว่า running time เป็น cubic

โปรแกรมที่มี running time เป็น logarithmic จะใช้เวลาเพิ่มขึ้นเป็นค่าคงที่เมื่อ n เพิ่มขึ้นสองเท่า และ

โปรแกรมที่มี running time เป็น $O(n\ log\ n)$ ใช้เวลาเพิ่มขึ้นกว่าสองเท่าเล็กน้อยเมื่อ $n$ เพิ่มขึ้นสองเท่า การเพิ่มขึ้นดังกล่าวมานั้นจะสังเกตเห็นได้ยากมากถ้าหากว่าสัมประสิทธิ์ของเทอมที่มีกำลังต่ำ ๆ มีค่าสูงมาก ๆ และ $n$ มีค่าไม่สูงมากพอ เช่นถ้าค่า $n = 10$ ถึง $n = 100$

สำหรับอัลกอริทึมแบบต่างในกรณีปัญหา maximum subsequence sum นอกจากนี้ยังเป็นเรื่องยากที่จะเห็นความแตกต่างระหว่าง linear และ $O(n\ log\ n)$ อีกวิธีที่ใช้ตรวจสอบว่าโปรแกรมเป็น $O(f(n))$ คือ คำนวณหาค่าของ $T(n) / f(n)$ สำหรับช่วงของค่า $n$ (ซึ่งปกติคือให้มีระยะห่างในอัตราส่วนของ 2 เท่า) เมื่อ $T(n)$ เป็น running time ที่เราวิเคราะห์ได้ ถ้า $f(n)$ เป็นคำตอบของ running time ที่ใกล้เคียงมาก (หรือถูกต้อง) แล้วค่าที่ได้จากการคำนวณจะ converge เข้าหาค่าคงที่ที่เป็นบวก ถ้าการประมาณค่า $f(n)$ เป็นค่าที่เป็นการ over estimate แล้วค่าที่จากการคำนวณจะ converge เข้าหาค่าศูนย์ และถ้า $f(n)$ เป็นการประมาณที่เป็นการ under estimate (ซึ่งผิด) แล้วค่าที่จากการคำนวณจะ diverge