Are there any real computaional problems which can be solved by time complexity of log(n) * log(n)?

• This is different from finding smallest element in sorted matrix, which is log(n) log(n) or 2log(n).

• There are can be some kind of pattern printing algorithm which can be made as ϴ(logn)^2 but I'm not sure if they are classified as Computational Problems.

CodePudding user response：

A range query on a d-dimensional range tree with k results runs in O(log^d(n) k) time. So a query that you know will result in a bounded number of results on a 2-d range tree runs in O(log^2(n)) time.

See https://en.wikipedia.org/wiki/Range_tree

CodePudding user response：

Dichotomic search in a sorted array when the indexes are processed as binary strings (bignums).