search

interview-preparation / what-we-do

0 stars 8 forks source link

[Big-O] Additional Problems #6 #33

Closed rygh4775 closed 5 years ago

rygh4775 commented 5 years ago

The following code computes the [integer] square root of a number. If the number is not a perfect square (there is no integer square root), then it returns -1 .It does this by successive guessing. If n is 100, it first guesses SO. Too high? Try something lower - halfway between 1 and SO. What is its runtime?

int sqrt(int n) {
    for (int guess = 1; guess * guess <= n; guess++) {
        if (guess * guess == n) {
            return guess;
        }
    }
    return -1;
}
btakeya commented 5 years ago

It tries the [integer] square root of n time while n is not a perfect square number. It breaks out when n is a perfect square number but doesn't affect the time complexity. Thus, the time complexity of sqrt() is O(n).

btakeya commented 5 years ago

O(sqrt(n))