1

I'm trying to learn and understand how to find big O notation .

well, here I need to find big-O notation for these algorithms , and I did the calculating for the running time for these algorithms but I'm not sure if my attempt is correct or not.

1)

    x←1      → 1
for i←1 to n    
     j←1        
     while j<n     
           x← max(x, i*j)     
           j← 2*j         
return x      → 1

2)

x←1         → 1
for i←1 to n    
    x←max(x,i)        
for j← 1 to n2       
    x←max(x,j)       
return x                →1
stephan
  • 11
  • Your analyses are a bit informal, but correct. – Math1000 Sep 27 '16 at 02:09
  • @Math1000 both of them? they are 2 examples. – stephan Sep 27 '16 at 02:11
  • #1: You do $n$ loops involving $j$, each of which has the same length (why?) So this takes $n$ times the length of the $j$ loops, which you should compute. #2: I'm not sure what "n2" means, perhaps $n^2$? If so, then the first loop takes $n$ steps and the second takes $n^2$ steps, so the whole thing takes $n+n^2$ steps. What's the best possible big Oh notation for $n+n^2$? (Incidentally, "the best possible big Oh notation" is also called "big Theta notation".) – Ian Sep 27 '16 at 23:52

0 Answers0