Func5(n)
1 s=0;
2 i=6;
3 while (i < n^(5/2)) do
4 j=4;
5 while (j < 5i) do
6 s=s + i - j;
7 j=j + 9 ;
8 end
9 i=4 * i ;
10 end
11 return (s);
So far I got the upper bound for this function is O(n^(5/2)log(n)) and I am not sure if or not this is the closest upper bound we can get. And I have no clue how to show the lower bound with the same function.
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
The inner loop has linear growth till i, which is in $\Theta(i)$, How ever i grows exponentially to n, The trick here is to observe that $$\sum_{i = 0}^{n}2^i = 2^{i+1}$$ However, using a number greater than 2, (4 in our example), we get a number way smaller than $4^{(i+1)}$, namely $(4^{(i+1)}-1)/3$, in our case however, we are summing up till the sum is n, which means we are summing $\Theta(k = \log(N))$ steps and in each step we have linear growth to i, which is (using the trick) in $\Theta(4^{\log(n)+1}) = \Theta(n)$
Mathematically speaking: $$6*4^k = n^{5/2}$$ $$\log(6) + \log(4^k) = \log(n^{5/2})$$ $$\log(4^k) = \log(n^{5/2}) - \log(6)$$ $$ k = \frac{5/2\log(n) - \log(6)}{\log(4)} \in \Theta(\log(n))$$ And in everystep we are having a linear growth of j till i, which is in $$\sum_{k=0}^{log(n)}4^k = (4^{log(n)+1}-1)/3 \in \Theta(n)$$.
