-1
def exercise2(N):
    count=0
    i = N
    while ( i > 0 ):
        for j in range(0,i):
            count = count + 1
        i = i//2

How do we know the time complexities for both the while and for loop? Edit:Many of the users are sending me link to understand the time complexity using Big-OH analysis. I appreciate it but the only languages in CS i understand is python and all those explanations are using java and C++ which makes it hard for me to understand. If anyone could explain time complexity using python it would be great!

Dissy
  • 11
  • 1
  • 1
    Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Pranav Hosangadi Mar 24 '21 at 14:26
  • @Dissy It is quite common to have explanations given in other computer languages than what you might not be used to. It is incumbent on you to find the similarities and generalize to learn a topic. I would gamble that if you spent some time with the link above you would be able to dis-entangle the C code. Sorry for the `tough love`. – mccurcio Mar 24 '21 at 15:10
  • 1
    @oaxacamatt so i went through it and understood some of the concepts. Now using them i worked on this code. I just wanna verify if i reached the correct answer. Is the time complexity for this O(n)? – Dissy Mar 24 '21 at 20:02
  • @Dissy 1st Congrats on giving it the college try, 2nd I noticed you still had questions, Let's see... – mccurcio Mar 27 '21 at 18:35

1 Answers1

1

The inner loop (for) is running in i, and i is going down from N to 1 in log(N) steps at most. Hence, the time complexity is N + N/2 + N/4 + ... + 1 = N(1 + 1/2 + 1/4 + ... + 1/2^k) = \Theta(N). For the latter equation, you can suppose N = 2^k as we are computing the asymptotic time complexity.

OmG
  • 18,337
  • 10
  • 57
  • 90