Որ դեպքերում կարող է ArrayList-ի վերջում տարր ավելացնելը ունենալ ժամանակային բարդություն O(n)?

ArrayList-ի վերջում տարր ավելացնելը սովորաբար ունի ամորտիզացված ժամանակային բարդություն O(1), բայց որոշ դեպքերում կարող է լինել O(n): Դա տեղի է ունենում, երբ ներքին զանգվածը, որը պահում է տարրերը, լեցուն է և անհրաժեշտ է ընդլայնել այն:

Նոր տարր ավելացնելիս՝

• Եթե տեղ կա, տարրն ուղղակի ավելացվում է — O(1):
• Եթե տեղ չկա, ստեղծվում է մեծացրած չափի նոր զանգված (հաճախ 1.5-2 անգամ մեծ), և բոլոր առկա տարրերը պատճենվում են նոր զանգվածին — այս գործողությունը O(n):

Այսպիսով, տարր ավելացնելը կարող է ունենալ ժամանակային բարդություն O(n) հենց այն պահին, երբ ընդլայնվում է ներքին զանգվածը։