Running time of algorithm A is at least O(n²) – Why is it meaningless?

T(n): running time of Algo A. We just care about the upper bound and lower bound of T(n) The statement: T(n) >= O(n^2)

Upper bound: Because T(n) >= O(n^2), then there’s no information about upper bound of T(n) Lower bound: Assume f(n) = O(n^2), then the statement: T(n) >= f(n), but f(n) could be anything that is “smaller” than n^2 , Ex: constant, n,..., So there’s no conclusion about lower bound of T(n) too

=> The statement is meaningless

Related Posts:

  1. Difference between Big-O and Little-O Notation
  2. What is tail recursion?
  3. What does O(log n) mean exactly?
  4. What does O(log n) mean exactly?
  5. Understanding Time complexity calculation for Dijkstra Algorithm
  6. Time complexity of a Priority Queue in C++
  7. Time Complexity of the Kruskal Algorithm?
  8. Example of O(n!)?
  9. Big O, how do you calculate/approximate it?
  10. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  11. O(n log n) vs O(n) — practical differences in time complexity
  12. What is a good Hash Function?
  13. Is log(n!) = Θ(n·log(n))?
  14. How to calculate big-theta
  15. What is the time complexity of while loops?
  16. What is the difference between a heuristic and an algorithm?
  17. Which is better: O(n log n) or O(n^2)
  18. Asymptotic Notation – does n (log n) (log n) simplify?
  19. Big Oh for (n log n)
  20. What is the big-O of the function (log n)^k
  21. Why is O(n) better than O( nlog(n) )?
  22. the asymptotic growth of n choose floor(n/2)
  23. Which algorithm is faster O(N) or O(2N)?
  24. A tool for calculating the big-O time complexity of Java code? [closed]
  25. Difference between Big-Theta and Big O notation in simple language
  26. How are the following functions O(N^3)?
  27. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  28. Are there any real O(n^n) algorithms?
  29. In a triangulated isometric grid, what triangle is a given point in?
  30. Using prevNext Modx Addon
  31. :wq! command in vim
  32. how to set the background color of the status bar during the launching phase [duplicate]
  33. api-ms-win-crt-runtime-l1-1-0.dll is missing when opening Microsoft Office file [closed]
  34. When is K 1024 and when is it 1000?
  35. What is a MIME type?
  36. Logitech/LGHUB Lua – Loop with break
  37. are there dictionaries in javascript like python?
  38. How can I convert MP3 file to a Base64 encoded string? [closed]
  39. Understanding The Modulus Operator %
  40. Understanding the main method of python [duplicate]
  41. Dial pad to get phone number (with Android button images)
  42. TypeError: only integer scalar arrays can be converted to a scalar index with 1D numpy indices array
  43. How is the AND/OR operator represented as in Regular Expressions?
  44. TypeError: only integer scalar arrays can be converted to a scalar index with 1D numpy indices array
  45. Istio Ingress resulting in “no healthy upstream”
  46. Why is it not possible to fake an IP address?
  47. How to open a “-” dashed filename using terminal?
  48. Substring in excel
  49. What is a LAMP stack?
  50. What is a sanity test/check
  51. What is the difference between POST and PUT in HTTP?
  52. What is the difference between POST and PUT in HTTP?
  53. How to find Google’s IP address?
  54. What exactly is a VBO in OpenGL?
  55. What and where are the stack and heap?
  56. ping response “Request timed out.” vs “Destination Host unreachable”
  57. Authentication versus Authorization
  58. What is a reverse shell?
  59. How does npm start work? What all processes are happening in the background?
  60. What is an instance variable in Java?
  61. What is the := operator?
  62. How do I check if an array includes a value in JavaScript?
  63. Discord music bot not working
  64. What does “:=” mean in Pseudocode? [closed]
  65. Why am I getting error for apple-touch-icon-precomposed.png
  66. No results found on kibana -> discover
  67. What is Xpenology? Is it Linux related thing?
  68. What is a loop invariant?
  69. What is a loop invariant?
  70. Why do we need virtual functions in C++?
  71. Kadane’s algorithm explained
  72. What is a CSRF token? What is its importance and how does it work?
  73. Unfamiliar symbol in algorithm: what does ∀ mean? [closed]
  74. Create blank image in Imagemagick
  75. Official definition of CSCI (Computer Software Configuration Item)
  76. How could I ping @here in Discord.py?
  77. Python Math – TypeError: ‘NoneType’ object is not subscriptable
  78. What does %>% mean in R [duplicate]
  79. Dijkstra’s algorithm in python
  80. super() in Java
  81. how to calculate binary search complexity
  82. Visual List of iOS Fonts?
  83. Dijkstra’s algorithm in python
  84. What is useState() in React?
  85. TCP vs UDP – What is a TCP connection? [duplicate]
  86. How do I copy folder with files to another folder in Unix/Linux? [closed]
  87. ssh : Permission denied (publickey,gssapi-with-mic)
  88. Eclipse IDE for Java – Full Dark Theme
  89. Amazon Linux: apt-get: command not found
  90. Google Calendar API event insert always return 404 “not found” error
  91. ssh connect Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password)
  92. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
  93. Removing duplicates in lists
  94. What’s the syntax for mod in java
  95. what does O(N) mean [duplicate]
  96. What does the Java assert keyword do, and when should it be used?
  97. How to get rid of the “No bootable medium found!” error in Virtual Box? [closed]
  98. How do I fix a “Expected Primary-expression before ‘)’ token” error?
  99. Using getline() with file input in C++
  100. STDERR? What is it? What are its common uses?

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)