So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and extract Max will not have O(1) amortized cost.Insert and extract max have O(logn) as worst time complexity for binary heaps.
Let ci denotes real cost of i−th operation, and ai denotes amortized cost.
Let Φ(Di)=potential after i operations
ai= ci + Φ(Di) − Φ(Di−1) = log(n) + c*n - c*(n-1) = log(n) + c(n-n+1) = log(n) + c
So im unsure as to how to prove that this potential function does not get O(logn) insert amortized cost. O(logn) would mean all functions that are less than or equal to xlog(n) (x is any constant).log(n)+c is greater than log(n) but is it less than x(logn+c)? Any help would be appreciated.