What is the Time complexity of isPascal() method

user_8327440 0
Viewed 37
static int isPascal(int n) {
    int sum = 0;
    int nthVal = 1;
    while (sum < n) {
        sum = sum + nthVal;
        nthVal++;
    }
    return sum == n ? 1 : 0;
}

Here the function checks given number is pascal number or not. Pascal number is a number that is the sum of the integers from 1 to i for some i.

For example 6 is a Pascal number because 6 = 1 + 2 + 3

What will be the Time complexity of this function? Will it be O(logn) time? If so what will be base of log here?

time-complexity function performance
1 Answers

If you consider calculating the square root a O(1) operation, you can do this check in O(1), with the help of the formula for the sum of the first i natural numbers

sum(i) = (i^2 + i)/2

Now in your case you don't know i but you know sum(i), because that's your n you want to check if it's a pascal number. So you have

n = (i^2 + i) /2

or

i^2 + i - 2n = 0

Solving this quadratic equation with the respecitive formula gives

i = -1/2 + sqrt(2*n + 1/4)

You can discard the second solution to this equation, because i must be > 0 to be a valid solution. If that resulting i is an integer, n is a Pascal number. Otherwise it isn't.

From that formula also follows, your iterative solution is in O(sqrt(n))

user_37769270
Related