Computing time complexity in C [closed]

by

For comparison sorting we consider the number of comparisons, sorting complicated objects this usually dominates.

Your outer loop always runs count times, your inner loop always runs on average ~count / 2 times. Every iteration of the inner loop always does one comparison.

Hence you get best, worst and average case is count * count / 2 which means all of them do O(n²) and Ω(n²) and θ(n²) comparisons (having n = the count parameter).

It is not the worst sorting algorithm imaginable if it works (I didn’t care to test), but best comparison sorting algorithms achieve O(n log n) worst case. In practice a hybrid algorithm like Timsort would always outperform your code except for a handful of items.

More Related Contents:

  1. Time complexity of a recursive algorithm
  2. Finding out the duplicate element in an array
  3. What’s the time complexity of iterating through a std::set/std::map?
  4. Count number of digits – which method is most efficient?
  5. Reading and analyzing rooms from text file
  6. Program to cause 1 sec delay in C and than print stuff
  7. String compare function in C [closed]
  8. How to allocate aligned memory only using the standard library?
  9. Passing multidimensional arrays as function arguments in C
  10. How can I suppress “unused parameter” warnings in C?
  11. Check substring exists in a string in C
  12. How do you convert a byte array to a hexadecimal string in C?
  13. What does i = (i, ++i, 1) + 1; do?
  14. What is the purpose of the RBP register in x86_64 assembler?
  15. C libcurl get output into a string
  16. How can I find the number of elements in an array?
  17. Bind failed: Address already in use
  18. C – How to implement Set data structure?
  19. fork and existing threads?
  20. Octal number literals: When? Why? Ever? [closed]
  21. Is fmod() exact when y is an integer?
  22. Why we need Clobbered registers list in Inline Assembly?
  23. Why gets() is deprecated? [duplicate]
  24. Using true and false in C
  25. How to set the IP address from C in linux
  26. How can I create C header files [closed]
  27. C11 in GCC?
  28. Can a “container_of” macro ever be strictly-conforming?
  29. Is a += b more efficient than a = a + b in C?
  30. literal constant vs variable in math library

Leave a Comment