סיבוכיות זמן ריצה של לולאת while עם פעולות

מדעי המחשב ואלקטרוניקה
1

אשמח לעזרה בתרגיל הזה לא הבנתי הבנתי מה הזמן ריצה פה,
זה ניראה כאיל הזמן ריצה הגדול ביותר הוא n כי הפעולות בתוך לולאת while רצות n פעמים.
אבל יש לי הרגשה שזה לא קל כמו שאני חושב.

נתחו את סיבוכיות זמן הריצה של האלגוריתם הבא, כאשר ידוע שהפונקציה n(h) לוקחת
זמן ריבועי:

FOO(n):
	while n >= 1:
		x = h(n)
		print(x)
		n = n/4

אשמח לעזרה עם השאלה הנ"ל.

2

על מנת לקבל אינטואיציה התחלתית, אני מציע שתנסה לשחק עם מספר דוגמאות (מה קורה אם n=4 ומה אם n=9 וכו’). לאחר מכאן, במידה והתוכנית פשוטה, תנסה לבנות ביטוי מתמטי ממנו.
במקרה שלך, הלולאה רצה על n, מבצעת סדר של פקודות כלשהם וכל פעם מקטינה את n פי 4, כלומר הלולאה אינה רצה n פעמים כמו שציינת. כמו כן, הפעולה הראשונה בלולאה מתבצעת ב-O(n^2) ושתי הפעולות הנוספות בלולאה מתבצעות ב-O(1) ולכן סיבוכיות הזמן של הפעולה הינה:

O(n^2\log_4n)=O(n^2\log n)