educative.io

Confused about time complexity

Courses
,
#1

Why isn’t everything under
while j < var:
in log base 2 of n time? j is doubling each time in log base 2 of n time.

Thanks

#2

Hi @Wilson_So!

Thanks for reaching out. Let’s try to break down this problem.

Since j is immediately doubled in the while loop, it will be greater than var. You might be thinking that whether j is greater than var depends on their values, i.e., what if var is 100 and j is 2. Then j will be doubled to 4 but will still be less than var which is equal to 100. Well, actually, this can never be the case. Since var starts with 0 and j starts with 1,varclosely follows the value ofj`.

Hence the while loop will run at most once for each iteration of the outer for loop.

Let us know if this helps!

Regards,
Ayesha Basit
Developer Advocate | Educative.io

#3

Hi

but… can we say code is of time complexity O(n) and θ(log n) ?
for example if you modify the code to:

> n = 10  # can be anything
> sum = 0
> pie = 3.14
> j = 1
> for var in range(n):
>     while j < var:
>         sum += 1
>         j *= 2
> print(sum)

the result that sum print to the output for values of n = 10, 1000, … shows summation has been executed close to log2(n) times.

Thanks.