Question regarding time complexity !

Question

def logn(n):
while(n>1):
n = math.floor(n/2)
Here n = 8.

In the above code, the time complexity if O(log n). My question is if I put n/3 in place of n/2, will the time complexity remain as O(log n) ???

Answer 1

Your algorithm has a time complexity of O(log2(n)).
By changing n/2 to n/3, i'm pretty sure it will be O(log3(n)).

Answer 2

Harsha S
Using nested "for" loops or such, it is quite obvious :
for x in range(n) :
for y in range(n) :
[...] # in O(1)
This one is O(n^2), because there are n*n times the O(1) operations.

However, depending on the type of program you use, it will be harder (the one proposed by Levi is "harder").
I will explain it in my next post.

Answer 3

Levi & Harsha S

The complexity C(n) here can be dominated by a sequence (mathematically speaking) when n isn't a power of 3:

Let's say p = log3(n)
U(n) = 1 + U(ceil(n/3)) (1 for value assignation for n, the other for the next loop iteration)
So U(3**p) = 1 + U(3**(p-1))
So U(3**p) = p considering U(3**0)=0

We have 3**p <= n <= 3**(p+1)
So C(n) <= U(n) <= U(3**(p+1)) = p+1 <= log3(n) + 1
(with an equalty when n is a power of 3)

So we have a complexity of O(log3(n)+1), which is O(log3(n)).

(i'm writing this on my phone, sorry if there's any typo)
That is the idea for that kind of script.

Answer 4

Arthur Le Floch how do i calculate time complexity

Answer 5

Arthur Le Floch thank you

Answer 6

What do you mean under „the time complexity if O(log n)“?