זמן ריצה של בניית עץ AVL מ N איברם במקרה הגרוע?,ומיון ערימה

1-

זמן ריצה של בניית עץ AVL מ N איברם במקרה הגרוע

כתבתי שזה O (גדול ) של N LOG N

נעשה לולאה על כל ה N איברים(שזה N )

בתוכה,צריך למצוא את המקום להכנסה שזה O (גדול ) של LOG N (כי רצים על הרמות

אחרי ההכנסה(עדיין בלולאה) צריך לבדוק אם צריך לעשות גלגול -וזה גם O (גדול ) של LOG N

ואז אם צריך גלגול זה O של 1 כי זהמספר פעולות קבוע

סה"כ יוצא O(גדול ) של N LOG N

קיבלתי על זה תשובה חלקית

מדוע?

האם זה לא נכון?

שאלה 2-

אם יש מערך שבנוי בצורת ערמת מקסימום בעל N מספרים כלשהם,יכול להיות שיש אלגוריתם למיון שזמן ריצה שלו הוא O (גדול) של N ?

טענתי שלא יכול להיות , כי האלגוריתמים למיון ליניארי (דליים,בסיס וכו') הם רק כאשר יש לי טווח סופי של מספרים וכדומה, אבל כאשר יש N איברים בטווח לא ידוע , אי אפשר

האם יש דבר כזה?

תודה