Advertisement
AdrianMadajewski

Time complexity simple functions

Nov 13th, 2019
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.96 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. double timeTaken(int start, int end) {
  5.     return ((end - start) / CLOCKS_PER_SEC);
  6. }
  7.  
  8. // O(n^2)
  9. int f1(int x) {
  10.     int res = 0;
  11.     int a = 1;
  12.     for(int i = 1; i <= x; ++i) {
  13.         res += i;
  14.         for(int j = 1; j <= x; j++) {
  15.             a *= 1;
  16.         }
  17.     }
  18.     return res;
  19. }
  20.  
  21. // O(n)
  22. int f2(int x) {
  23.     int res = 0;
  24.     for(int i = 1; i <= x; ++i) {
  25.         res += i;
  26.     }
  27.     return res;
  28. }
  29.  
  30. // O(1)
  31. int f3(int x) {
  32.     return (int) (x * (x + 1) / 2.0);
  33. }
  34.  
  35. int main(void) {
  36.    
  37.     clock_t start;
  38.     clock_t end;
  39.    
  40.     start = clock();
  41.     printf("f1(): %d in time: %f\n", f1(100), timeTaken(start, end));
  42.     end = clock();
  43.    
  44.     start = clock();
  45.     printf("f2(): %d in time: %f\n", f2(100), timeTaken(start, end));
  46.     end = clock();
  47.    
  48.     start = clock();
  49.     printf("f3(): %d in time: %f\n", f3(100), timeTaken(start, end));
  50.     end = clock();
  51.    
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement