Computational Complexity of SIFT descriptor?

Question

The SIFT descriptor is a local descriptor that introduced by David Lowe. This descriptor can be splitted up into multiple parts:

1- Constructing a scale space

2- LoG Approximation

3- Finding keypoints

4- Get rid of bad key points

5- Assigning an orientation to the keypoints

6- Generate SIFT features

So, my question is:

What is the computational complexity of SIFT descriptor? something like O(2n+logn)

Answer 1

Here's a paper that talks exactly about this.

The actual time complexity for a n by n image is apparently

where x is the neigborhood of the tile,pi,po are the number of input, output pins of the chip, α,β,γ are the feature fractions, and Γ0,Γ1,Γ2 are the input, compute, output clocks.