code_junkie

Plain English explanation of Big O

Nov 13th, 2011
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.01 KB | None | 0 0
  1. 5! = 5 * 4 * 3 * 2 * 1 = 120
  2. 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
  3. 7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040
  4. ...
  5. 25! = 25 * 24 * ... * 2 * 1 = 15,511,210,043,330,985,984,000,000
  6. ...
  7. 50! = 50 * 49 * ... * 2 * 1 = 3.04140932... × 10^64
  8.  
  9. actualAlgorithmTime(N) ∈ O(t(N)) ("the problem is O(t(N))")
  10.  
  11. actualAlgorithmTime(N)
  12. ───────────────────── == constant ("we'll never do worse than [const]*t(N)")
  13. t(N)
  14.  
  15. "For large enough inputsize=N, if I double the input size...
  16. ... I double the time it takes." ( O(N) )
  17. ... I quadruple the time it takes." ( O(N^2) )
  18. ... I add 1 to the time it takes." ( O(log(N)) )
  19. ... I don't change the time it takes." ( O(1) )
  20.  
  21. int Sum(int*arr,int size){ int sum=0;while(size-->0) sum+=arr[size]; return sum;}
  22.  
  23. void Combination(int*arr,int size)
  24. { int outer=size,inner=size;
  25. while(outer -->0) {
  26. inner=size;
  27. while(inner -->0)
  28. cout<<arr[outer]<<"-"<<arr[inner]<<endl;
  29. }
  30. }
Add Comment
Please, Sign In to add comment