CODEWITHSUNDEEP
algorithmtime-complexitybig-o
enesanbar
enesanbar

Reputation: 49

Time-complexity of while loop in big-O

I'm having trouble indicating the time complexity of a simple while loop in terms of input n.

The while loop executes as long as i < n and i is incremented by one more than the number of previous iteration. For example, in the 2nd iteration, i is incremented by 1, in the 3rd iteration, by 2, and so on... Essentially, the loop executes "final value of t" times.

func(n):
    i = 1
    t = 1

    while (i < n):
        i = i + t
        t = t + 1

My question is, how can I indicate the time complexity of this algorithm in big-O notation?

Upvotes: 0

Views: 783

Answers (1)

Matthew Pope
Matthew Pope

Reputation: 7669

Essentially, the loop executes "final value of t" times.

You're halfway there. You know that the loop executes t times, now you just need to solve for t.

Your loop will end when the sum of 1..t is greater than or equal to n. By solving the summation, we can express this as 

t*(t-1)/2 >= n

By rearranging the equation to show t in terms of n, we get

t >= 1/2 (1 - sqrt(1 + 8 n))

But, we also know that the loop ends at the lowest (first) value of t that satisfies the inequality. Let us call that value tn. If tn is the first value that satisfies the inequality, then tn-1 is the last value that satisfies the opposite inequality.

tn - 1 <= 1/2 (1 - sqrt(1 + 8 n))

From this, we know that t is bounded above and below by some function of sqrt(n) and some constants. So then t is Θ(sqrt(n)), which means t is also O(sqrt(n)).

Upvotes: 3

Related Questions