Approximate square root from algorithm time complexity
C(++), 93 Bytes

My solution:

int s(int a){int b=0;for(int i=1&lt;&lt;15;i&gt;0;i/=2){if((b+i)*(b+i)&lt;=a)b+=i;else{for(int j=1;j&lt;i;j*=2);}}return b;}


It is O(n) for a = 0xFFFF..., and O(n^2) for a = 0x1000...
And it returns floor(sqrt(x)), which is an approximation of sqrt(x)

However, If you want an algorithm that works in O(n) time, you can shave off 28 bytes.

For test cases, append:

int main()
{
    int a = 1024;
    return s(a); //returns sqrt(1024) = 32
}