Search code examples
time-complexitybig-onotation

time complexity for loop justification

Hi could anyone explain why the first one is True and second one is False?

enter image description here

Solution

  • First loop , number of times the loop gets executed is k times, Where for a given n, i takes values 1,2,4,......less than n.

                  2 ^ k <= n
              Or,  k <= log(n).

    Which implies , k the number of times the first loop gets executed is log(n), that is time complexity here is O(log(n)).

    Second loop does not get executed based on p as p is not used in the decision statement of for loop. p does take different values inside the loop, but doesn't influence the decision statement, number of times the p*p gets executed, its time complexity is O(n).