2

This is written in pseudocode. We have an Array A of length n(n>=2)

int i = 1;

while (i < n) { 
    if (A[i] == 0) { 
        terminates the while-loop;
    }
    doubles i
}

I am new to this whole subject and coding, so I am having a hard time grasping it and need an "Explain like im 5". I know the code doesnt make a lot of sense but it is just an exercise, I have to determine best case and worst case.

So in the Best case Big O would be O(1) if the value in [1] is 0.

For the worst-case scenario I thought the time complexity of this loop would be O(log(n)) as i doubles. Is that correct? Thanks in advance!

aurora
  • 23
  • 4

1 Answers1

1

For Big O notation you take the worse case scenario. For the case where A[i] never evaluates to zero then your loop is like this:

int i = 1;
while(i < n) {
  i *= 2;
}

i is doubled on each iteration, ie exponential growth.

Given an example of n=16

the values of i would be: 1 2 4 8 wouldn't get to 16

4 iterations

and 2^4 = 16

to work out the power, you would take log to base 2 of n, ie log(16) = 4

So the worst case would be log(n)

So the complexity would be stated as O(log(n))

Angus Comber
  • 9,316
  • 14
  • 59
  • 107
  • 3
    Big-O does not mean worst-case, nor is big-O notation reserved to be used only when describing worst-case algorithmic complexity. For example, OP is perfectly correct in saying that the best-case scenario is *O(1)*. – Berthur Dec 30 '22 at 14:02
  • @Berthur wiki article on Big-O states: "A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function." – Angus Comber Dec 30 '22 at 16:31
  • 1
    That is true, but it's not the same thing. The best-case complexity of an algorithm is its own function, so you can describe its growth rate using big-O, Ω or Θ as you would any function. That big-O is only "allowed" to describe best-case scenarios is a common misconception. (Btw, this discussion concerns only the first sentence of your answer, the rest seems great.) – Berthur Dec 30 '22 at 16:42