מורכבות של המודל עץ החלטה תלוי ב-

אין קשר בין מורכבות המודל לדיוק או לשגיאה (לפחות לא קשר ישיר). מספר הקודקודים בעץ מראה על מספר הפיצ'רים בהם נעשה שימוש במודל. ככל שיש יותר פיצ'רים המודל מורכב יותר ולוקח יותר זמן.