I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :)
Im a computer science student currently taking on Introduction to computer science, we recently learned about Big O and its formal definition. While looking at exercises, me and my friends had problem agreeing on the correct most Precise upper bound for this function
Pseudocode : Function foo(L is list) n = length of L Do while n > 0 n = n floor division over 2 Do for i=0 upto i=n-1 Something with complexity of O(1) End for End while return L Python: def foo(L:list): n = len(lst) while n>0: n = n//2 for i in range(n): # some O(1) code return L
My attempt: So we know that the innermost loop in relative to n at Log(n) - 1 times, then we also know the outer while loop runs Log(n) times.
so that gives us O((Log(n))^2) time complexity
My friend's attempt:
The innermost loop is a simple for loop over n so that is of time complexity of O(n) and the outer most loop runs at Log(n) times which gives us O(nlog(n))
at this point I'm Completely lost , How does the inner loop give us O(n) if its loop times is determined by n which is reduced to half each time ? as in this is not a simple nested loop that loop over the same number of iterations A clarification is much much much appreciated