Cost calculation and finding the big O notaion

sajithwi 0
Viewed 40

When calculating the cost to identify the Big O notation of this code, should I count following line too?

if(n == 0): print("Incorrect index No ")

if yes how to connect it with the loop

def FindFibonacci(n):
    

    if(n == 0):
        print("Incorrect index No ")
        
           
    else:
        
        n1 = 0
        n2 = 1
        x = 0
        while (x<n):
            print(n1)
            fib = n1 + n2
            n1 = n2
            n2 = fib

            x = x+1
            
num = int(input("How many Fibonacci sequences you want? "))  

FindFibonacci(num)
big-o algorithm python
2 Answers

Yes, when calculating the cost to identify the Big O notation of this code, you should also take the following line into account:

if(n == 0):
    print("Incorrect index No ")

It is not customary to include print statements in a function of which you want to identify the time complexity, but since the output string has a constant number of characters, we may assume it executes in O(1).

how to connect it with the loop?

The evaluation of the if condition (n == 0) has O(1) time complexity. When that condition is true, the print statement adds O(1) time complexity and the loop is not executed. So the overall time complexity for that particular case is O(1 + 1) = O(1).

For the case where the if condition is not true, the loop gets executed, so you need to find out what the loop's time complexity is. You'll find it is O(n). So in total you have O(1 + n) which still is O(n).

Taking all cases together -- including where n is 0 -- we get O(1 + n) which is O(n).

trincot0

Let us recall that

f(n) = O(g(n)) if there are constants c and N such that for all n≥N, |f(n)|≤g(n).

So one can safely ignore all special cases arising below some bounded value, and here the case of n=0 is quite irrelevant (you don't even evaluate its cost).

Other example:

if n < 1000 then print(n!) else print('Overflow')

has complexity O(1).

Yves Daoust0
Related