educative.io

Confused about time complexity


#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