On the cost of optimal alphabetic code trees with unequal letter costs

For some k≥2k≥2 let d=(d1,d2,…,dk)∈R>0k. We denote the concatenation of kk vectors a1,a2,…,ak∈⋃n≥0Rn by a1a2⋯ak and use ϵϵ to denote the empty vector.We consider a recursively defined function Dd:⋃n≥0Rn→R∪{−∞} with Dd(ϵ)=−∞, Dd((a))=a for a∈Ra∈R and Dd(a)=min{max{Dd(ai)+di∣1≤i≤k}∣a=a1a2⋯ak with ai∈⋃m=0n−1Rm for 1≤i≤k} for a∈Rn with n≥2n≥2.The function Dd equals the cost of an optimal alphabetic code tree with unequal letter costs and the above recursion naturally generalizes a recursion studied by Kapoor and Reingold [S. Kapoor, E.M. Reingold, Optimum lopsided binary trees, J. Assoc. Comput. Mach. 36 (1989) 573–590]. If z(n) denotes the vector consisting of n≥0n≥0 zeros, then let f(α)=max{i∈N0∣Dd(z(i))≤α} for α∈Rα∈R. Let d=min{d1,d2,…,dk}d=min{d1,d2,…,dk} and D=max{d1,d2,…,dk}D=max{d1,d2,…,dk}. Our main result is that Dd(z(∑i=1nf(ai)))≤Dd(a)≤Dd(z(∑i=1nf(ai)))+6D−2d for a=(a1,a2,…,an)∈R≥0n. This result is useful for the analysis of the asymptotic growth of Dd.