Time complexity of fun()?
The inner loop does n
iterations, then n/2
, then n/4
, etc. So the total number of inner loop iterations is:
n + n/2 + n/4 + n/8 + ... + 1
<= n * (1 + 1/2 + 1/4 + 1/8 + ...)
= 2n
(See Geometric series), and therefore is O(n).
For an input integer n,
for i=n, j
loop will run n
times,
then for i= n/2, j
loop will run n/2
times,
.
.
so on,
.
.
till i=1
, where j
loop will run 1 time.
So,
T(n) = (n + n/2 + n/4 + n/8 + ...... + 1)
T(n) = n(1 + 1/2 + 1/4 + 1/8 + ..... + 1/n) .....(1)
let 1/n = 1/2^k
so, k = logn
now, using summation of geometric series in eq 1
T(n) = n((1-1/2^k) / 1-1/2)
T(n) = 2n(1-1/2^k)
using k = logn
T(n) = 2n(1-1/2^logn)
now for larger value of n
, logn
tends to infinite and 1/2^infinite will tend to 0.
so, T(n) = 2n
so, T(n) = O(n)