The code I am trying to find the time complexity of is
int i=1,s=1;
while (s<=n)
i++
s+=i;
print("*")
I traced it with n = 10 and, if I'm doing it correctly, this runs 4 times for this instance. I cannot figure out what the general complexity would be, I keep thinking log base2(n) but this doesn't exactly work. Would really like to know how to find this or if it is just some simple equation I'm not thinking of.
You will need to use the Gaussian summation formula which calculates the sum of the first k natural numbers with k being a natural number:
1 + 2 + 3 + 4 + .. + k = ((k + 1)*k)/k = (k² + k) / 2
e.g. for k = 4:
1 + 2 + 3 + 4 = ((4 + 1)*4) / 2 = (5 * 4) / 2 = 20 / 4 = 10
If you look at your code you will see that s is exactly that sum.
The while loop runs till s <= n. s can be described by above formula as i is 1, then i = 2, then i = 3 and so on. So you can substitute s with above formula and get (i² + i) / 2 <= n. You know n = 10.
Therefore:
(i² + i) / 2 <= 10 <=>
i² + i <= 20 <=>
i² + i - 20 <= 0
Solve that (e.g. using "midnight formula" as we call it in Germany) and you get the solutions i <= 4 and i <= -5. i <= -5 obviously does not make sense in your example so 4 will be your solution.
You can generalize and approximate that (solve the quadratic equation i² + i - n <= 0) following the rules of big-O notation and you will have your runtime which will be O(n^1/2) or Theta(n^1/2) to be exact.
i follows an arithmetic progression of initial term 1 and common difference 1. s is the prefix sum of i (values 1, 3, 6, 10, 15, 21, ...). The general term is i(i+1)/2.
Now the loop runs as long as s≤n. We obtain the corresponding i by solving
i(i+1)/2 = n
and taking the integer part,
i = floor(√(2n+1/4) - 1/2).
As i represents the number of iterations of the loop, the complexity is of order Θ(√n).