0

I am new to the whole world of time complexity. So, I tried to read my textbook on data structures and tried to work on a problem set. I couldn't get the correct answer but I am not bothered by the answer. I want to really get the concept of calculating time complexity of algorithms. I tried the following problem set. Please help me out and kindly advise me on my error.

def program1(x):
    total = 0
    for i in range(1000):
        total += i

    while x > 0:
        x -= 1
        total += x

    return total

enter image description here

Calculate the best case and worst case time complexity of the above function.

Melissa
  • 41
  • 9
  • 1
    I dont understand that explanation ...I would answer that the best case complexity is `n=0` **=>** `O(1000)=>O(1)` and worse case is `n=HUGE` **=>** `O(1000+n) => O(1+n) => O(n)` I dont get where they are getting 3003 from ... and 5n from ... – Joran Beasley Jul 20 '16 at 16:28
  • 3
    If those "correct answers" at the bottom are from an answer key, this wasn't a very well thought-out assignment. The "best case" answer is an absolute number, while the "worst case" is a function of n. That's not consistent, and it's not how best- or worst-case analysis works. Also, we seem to be assigning arbitrary integer costs to computational steps and adding them up to produce uninformative constants and coefficients. Big-O analysis doesn't do that, and if you need something more detailed than Big-O analysis, you can't just assign a cost of 1 to everything. – user2357112 Jul 20 '16 at 16:30
  • @JoranBeasley I guess its right? Check out my answer. – hashcode55 Jul 20 '16 at 16:48

0 Answers0