א. נתונה השגרה הבאה שהקלט שלה הוא שני מערכים ממוינים A ו-B בגודל \(n\) (האינדקס הראשון בשניהם הוא 1, ניתן להניח שהאיברים בכל אחד מהמערכים הם ייחודיים, כמו-כן נסמן ++i למשל כקיצור להצבה i ← i + 1):

Count_What(A,B,n)
  i ← 1; j ← 1; s ← 0
  While i ≤ n and j ≤ n
    If A[i] < B[j] then
      i++
    Else if A[i] > B[j] then
      j++
    Else // A[i] == B[j]
      s++
      i++
      j++
  Return s

1. מה מחזירה השגרה כפונקציה של הקלט שלה? נדרשת תשובה מילולית של שורה אחת קצרה.
2. נסחו שמורת לולאה מתאימה באמצעותה ניתן להוכיח זאת (אין צורך להוכיח את שמורת הלולאה). יש לנסח את השמורה כתנאי מדויק המנוסח באמצעות המשתנים המופיעים בשגרה. נדרשת תשובה של שתי שורות לכל היותר.
3. נתחו בקצרה את סיבוכיות השגרה.

ב. הוכיחו או הפריכו את הטענה הבאה: לכל \(f,g\) פונקציות מהטבעיים לטבעיים, אם \(f(n) = O(g(n))\) אז \(lg(f(n)) = O(lg(g(n)))\).