מקרה שלישי - אם מתקיים formula_48. במקרה זה, התו החדש שנוסף אינו המשך של הרישא הקודמת, ולכן נחפש רישא קצרה יותר. מכיוון שהרישא הקודמת שווה לסיפא הקודמת, אזי הסיפא הארוכה ביותר המתאימה לרישא הארוכה ביותר ברישא הקודמת, היא גם סיפא של הסיפא הקודמת. מההנחה שהאלגוריתם פועל עבור קלטים קטנים, מתקיים שאורך הסיפא החדשה המתקבלת הוא המקסימלי, ולכן כל &lt;math&gt;A[i'] &lt;k לא יכול להיות אורך הסיפא שאינה כוללת את התו האחרון. כלומר - גם אם האלגוריתם לא ימצא בשלב זה את אורך הסיפא הוא יתחיל באיטרציה הבאה עם &lt;math&gt;i", ולכן האלגוריתם תמיד יגיע בסופו של דבר למקרה הראשון או השני.
נוכיח שלא קיים &lt;math&gt;i"=A[i']&lt;k כך ש-k הוא האורך של הסיפא הארוכה ביותר הנגמרת ב-formula_34 ומתאימה לרישא. אם זה אכן היה מתקיים, אז לפי הגדרה formula_50, אבל מכיוון ש-formula_51 הוא אורך הסיפא הארוכה ביותר המתאימה ל-formula_33, וגם לפי הטרנזיטיביות הסיפא הנגמרת ב-formula_34 זהה לסיפא הנגמרת ב-formula_33, אז למעשה formula_55, וזאת אומרת שאורך הסיפא המקסימלית הנגמרת ב-formula_33 היא לפחות k, בסתירה לכך שהנחנו שהאלגוריתם צודק עבור קלטים קטנים. זאת גם למעשה ההוכחה ש-formula_33הוא חסם עליון לאורך הסיפא, שהרי formula_58 עבור formula_33 כלשהו.
הוכחת זמן ריצה.
זמן הריצה הכולל של האלגוריתם הוא formula_60, כאשר הזמן הדרוש לבניית טבלה של התבנית הוא formula_61 וזמן החיפוש הדרוש הוא formula_62. נוכיח:
אלגוריתם.
כאשר אנחנו מבצעים את החיפוש עצמו, בכל איטרציה של כל אחת מהלולאות יש לפחות קידום אחד של i, כלומר לא קיימת איטרציה בה i לא קודם. בנוסף, כל איטרציה של הלולאות מפעילות formula_63 פעולות, ולכן בסך הכל יש לכל היותר formula_62 פעולות.
טבלה.
נסמן מונה C1 הסופר כמה פעמים עודפות האלגוריתם ביקר בתא בודד, ומונה C2 הסופר כמה פעמים האלגוריתם ביקר פעם בודדת. מתקיים formula_65 מכיוון שיש n+1 תאים בטבלה. כפי שצוין קודם, מתקיים formula_66, וגם formula_67 אם ורק אם קיימת איטרציה אחת בדיוק (כלומר C2 מקודם). בנוסף, מתקיים formula_68, כלומר במקרה הגרוע יש לולאה יורדת. נחבר את התנאים - על מנת שיתקיים formula_69 צריך שיתקיים formula_70 (לפי התנאי הראשון), ועל מנת שנוכל לקדם את C1, צריך שיתקיים formula_71. בסך הכל, על מנת לקדם את C1 יש לקדם את C2, ולכן מתקיים formula_72, ומספר האיטרציות הכולל קטן מ-formula_73, או formula_62, כנדרש.
גרג מקיו
גרג מקיו (באנגלית: Greg McHugh) נולד ב-5 בינואר 1980) הוא שחקן ותסריטאי סקוטי. מקיו הוא היוצר, הכותב וכוכב הסדרה הקומית "Gary: Tank Commander" של ערוץ BBC1. הוא שיחק בתפקיד הווארד בסדרה הקומית "בשר טרי" של ערוץ 4.
ביוגרפיה.
גרג מקיו נולד במורנינגסייד שבעיר אדינבורו שבסקוטלנד. אביו היה עובד מדינה ואימו הייתה מורה. הוא הצעיר במשפחה בת שלושה בנים.
מקיו למד בבית ספר היסודי סנט פיטר, ואחר כך בבית ספר התיכון St Thomas of Aquin. הוא למד מינהל עסקים באוניברסיטת סטירלינג, ולמד משחק באקדמיה הסקוטית המלכותית למוזיקה ודרמה בגלאזגו.
מקיו הופיע בתפקיד קטן בפרק "Faimly" בסדרה הקומית "Still Game" בדמות חבר המבקר חולה השוכב לצדו של וינטון אינגרם.
בסרט הטלוויזיה "Not Safe for Work" שיחק מקיו בתפקיד ג'וש אלווי.
ב-2010 הופיע מקיו בפרק "Don the Musical" בסיטקום "How Not to Live Your Life". הוא שיחק בתפקיד רנדי, שחקן בתיאטרון חובבים המגלם את דמותו של צ'ארלי באביט בגרסת המחזמר של "איש הגשם". עוד ב-2010 השתתף בשני פרקים של הסדרה "Rab C. Nesbitt" בתפקיד ליאם.
ב-2011 הופיע מקיו בתוכנית ההתרמה "Red Nose Day" בה דיווח על גיוס הכספים בסקוטלנד שנערך עבור הקומיק ריליף.
על כתיבת התסריט לסדרה " Gary: Tank Commander" היה מקיו מועמד לפרס באפט"א הסקוטי.
בין 2011 ל-2016 כיכב מקיו בתפקיד הווארד בסדרה הקומית של ערוץ 4 "בשר טרי".
ב-2013 הופיע מקיו במיני-סדרה "Dates" של ערוץ 4.
עוד ב-2013 שיחק בפרק ספיישל חג המולד של הסדרה " Bad Education" בתפקיד הומלס בשם בונהד.
ב-2014 הופיע מקיו בתפקיד מלקולם בסרט "Marvellous" של ה-BBC.
מ-6 בדצמבר 2014 עד 11 בינואר 2015 שיחק מקיו בתפקיד סמי בהפקה מוזיקלית (pantomime) של "פיטר פן" בתיאטרון קינג'ס בגלאזגו.
ב-2016 וב-2017 גילם מקיו את אדי סקוט בסדרת הדרמה "סוג א'" של ערוץ BBC One.
מה-20 עד 22 באוקטובר 2016 שיחק שוב בתפקיד גארי בהפקה בימתית של הסיטקום "Gary: Tank Commander" באולם ההידרו בגלאזגו.
חיים אישיים.
מקיו חי בהוב שבמזרח סאסקס עם אשתו קייטי. לבני הזוג יש שני ילדים.
גרג מק'יו
יו מסקלה
יו מסקלה (באנגלית: Hugh Masekela; 4 באפריל 1939 – 23 בינואר 2018) היה מוזיקאי פופ, ג'אז, דיסקו, אפרו-פופ, ו-R&amp;B, חצוצרן, נגן פלוגלהורן וקורנית, יוצר, מלחין וזמר אקטיביסט דרום אפריקאי. הוא היה חלוץ הג'אז בדרום אפריקה והיה אחד מנגני הג'אז המצליחים בעולם. מסקלה שיתף פעולה עם אמנים שונים כולל מיילס דייוויס, מרים מקבה, פול סיימון ועוד, ויצר מספר להיטים בינלאומיים. מסקלה גלה לשלושים שנה מדרום אפריקה עקב מחאתו נגד שלטון האפרטהייד. הוא השתמש במוזיקה ובהופעות שלו על מנת לתקוף את משטר האפרטהייד שהיה אחראי על גירושו מדרום אפריקה. מסקלה היה פעיל פוליטי גם כאשר חי בארצות הברית, ואף לאחר שחזר למולדתו בעקבות סיום האפרטהייד. מאבקו נגד האפרטהייד כולל שירים כ-“Soweto Blues", “Bring Him Back Home”. בשנת 1968, זכה שירו "Grazing in the Grass" בתואר הלהיט מספר אחד בארצות הברית במצעד הבילבורד לשירי פופ.
ביוגרפיה.
נעוריו.
יו מסקלה נולד בקווהגוקה, וויטבנק שבדרום אפריקה. אביו, טומס סלנה מסקלה, היה מפקח בריאות ופסל, ואמו, פאולינה באוורס מסקלה, הייתה עובדת סוציאלית. מסקלה גדל בעיקר עם סבתו שניהלה את ה"שיבין" – בר לא חוקי עבור לקוחות שחורים דרום אפריקנים בביתה (עד 1961, בדרום אפריקה שתייה הייתה לא חוקית עבור כל בן אדם אשר אינו לבן).
אהבתו למוזיקה התפתחה בילדותו בהשראת הקשר שלו עם דודו שנהג להשמיע לו מוזיקה של עבדים שהתארחו ב"שיבין", הבר המשפחתי. מסקלה נחשף לאמני הג'אז הגדולים ביניהם לואי ארמסטרונג, דיוק אלינגטון וגלן מילר. החיבור בין מוזיקה לאלכוהול השפיע על חייו של מסקלה שהתחיל לשתות בגיל 13.
מסקלה הביע רצון ללמוד לנגן בחצוצרה לאחר שראה את הסרט "איש צעיר עם חצוצרה". במטרה לעזור למסקלה לשפר את ההתנהגותו, הכומר טרבור הדלסטון שעבד בפנימיה בה מסקלה למד והיה אקטיביסט נגד האפרטהייד, נתן לו במתנה חצוצרה שקיבל מלואי ארמסטרונג. מסקלה התחיל לנגן בה בגיל 14.
קריירה.
באמצע שנות ה-50 מסקלה הצטרף ללהקתו של אלפרד הרברט, אשר ניגנה מוזיקת ג'אז אפריקאית ביוהנסבורג. לאחר מספר שנים של נגינה, מסקלה הקים להקת הג'אז הדרום אפריקאית, ‘The Jazz Epistles’ בה הופיע אמן דרום אפריקאי אחר מפורסם, הפסנתרן והמלחין, אבדולה איברהים. השניים הקליטו יחדיו את תקליט הג'אז המודרני הראשון בדרום אפריקה עם להקת נגנים שחורים. בשנות ה-60, כתוצאה מטבח שארפוויל, אירוע בו התעמתו כוחות משטרה חמושים עם מפגינים שחורים שהיווה כנקודת מפנה דרמטית בהיסטוריה של דרום אפריקה, הלהקה הפסיקה לנגן ולהקליט שירים. באותן השנים מסקלה היה אקטיביסט, ובאמצעות המוזיקה שלו פעל כנגד האפרטהייד בדרום אפריקה. לאחר שלמד כי פעילותיו כנגד האפרטהייד שמות אותו בסכנה, מסקלה עזב לניו יורק שם הצטרף לחבריו הזמרת מרים מקבה והאקטיביסט הארי בלפונטה. בניו יורק, הוא קיבל מבלפונטה מלגת לימודים, למד לנגן מוזיקה קלאסית בחצוצרה בבית הספר למוזיקה במנהטן בין השנים 1960–1964, ועבד משרה חלקית בחנות תקליטי מוזיקה של בלפונטה.
מסקלה ומקבה התאהבו והתחתנו בשנת 1964. שנתיים לאחר מכן, בשנת 1966 התגרשו. ביחד הם הספיקו להופיע במחזמר "קינג קונג" ולהקליט אלבום "The Many Voices of Miriam Makeba".
בשנותיו המוקדמות בניו יורק, בילה מסקלה את לילותיו במועדוני הג'אז המפורסמים ונחשף לענקי מוזיקת הגאז' האמריקאים: מיילס דייוויס, ג'ון קולטריין, ת'לוניוס מונק, צ'ארלס מינגוס ומקס רואץ'. הוא חלם להיות מוזיקאי ג'אז כמוהם. מיילס דייוויס ייעץ למסקלה לנסות לפתח סטייל משלו הכולל שילוב של מוזיקת ג'אז, ‘Soul’, ומוזיקה דרום אפריקאית – 'מבקנגה'.
המלצתו של מיילס דייוויס עזרה לקריירה של מסקלה. אלבום הסולו הראשון של מסקלה יצא בשנת 1963 ונקרא "Trumpet Africain". לאחריו עבר מסקלה לגור בלוס אנג'לס. בשנת 1967 הקליט מסקלה את שירו המפורסם “Up, Up and Away” בו הופיעו לצידו ג'ניס ג'ופלין, אוטיס רדינג, ראווי שנקר, הלהקה "The Who" וג'ימי הנדריקס. השיר בוצע במסגרת פסטיבל 'מונטריי פופ'. שנה לאחר מכן, יצא לאור השיר "Grazing in the Grass" שהפך להצלחה מסחררת וללהיט מספר אחד במצעד הבילבורד הוט 100 בארצות הברית. בשנת 1977 מרים מקבה הופיעה עם אחד משיריו של מסקלה, "Soweto Blues", על המאבק נגד אפרטהייד ובפרט עוסק במהומות בסווטו . השיר החדש זכה לפרסום ותהילה בינלאומית בזכות הופעתה.
במהלך שלושים השנים ששהה מחוץ לדרום אפריקה, גר מסקלה בליבריה, גינאה, גאנה ובוטסואנה, שם הקליט את שיריו עם מספר אמנים ולהקות אפריקאיות.
בשנת 1987, הופיע מסקלה לצידו של פול סיימון, מרים מקבה, ריי פירי ו-Ladysmith Black Mambazo כחלק ממסע הופעות לקידום האלבום "Graceland". בנוסף לכך, הוא היה חלק מיצירת המוזיקה עבור המחזמר 'סרפינה!' שהופיע בברודוויי.