Time-complexity of while loop in big-O

Question

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?

• Ian Mercer: Take a look at en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF which should give you a hint at how you can calculate how many times the loop will run

Answer 1

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)).