Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 7

(a)

When n is not a power of 2, we can make the matrix dimensions as power of 2 by adding at most n-1rows and columns. Therefore, the ratio m/n is at most (2n-1)/n = 2 - 1/n.

(b)

The new rows should be added at the bottom and the new columns at the right. All entries in these rows and columns should be zero.

(c)

Since m is less than 2n, the complexity as a function of n is also Theta(n2.81).