Algorithms in O(n^2) vs O(n) [duplicate]

What you are asking about is a topic in computer science known as Algorithm Complexity Analysis. It is a very important topic to consider when writing algorithms, or solutions, in your programs because it relates to run-time, or how fast your computations will run.

Big-Oh, or O(n) relates to the upper-bound run-time for an algorithm to run. In this case, O(n) means for n-elements there will need to be all n-elements considered for the algorithms computation to complete, or linear. The range for this Big-Oh complexity is from constant time, O(1), to up O(n^n) for really large, and very slow computations. Also, consider equations such as the following:

y=10n+1
y=5n+10

These both are O(n) complexity because as the number of elements grow, the equation grows larger and larger because of it. We neglect the constants because the equation will grow larger and fast due to the variable, rather than due to the constant values which never change. Whereas, with equation as the following:

y=10n^2+5n+5

The complexity is going to be O(n^2) due to the 10n^2 being the largest growing element contributing to the equation growing faster. We drop the constants and consider the largest growing components to equations to evaluate complexity.

For Big-Omega complexity, we consider this the lower bound for Algorithm Complexity Analysis. For example, an algorithm can run as quick as Omega(n) (best case) but take as long as O(n^2) (worst case) this is common in analysis of sorting algorithms or searching algorithms.

In some cases, we want to write programs with algorithms that are efficient and faster for optimization reasons, especially when we want a quicker program for faster solutions or quicker run times.

The code example you provided is O(n) because it uses a for loop to iterate over n-elements. Consider a double for loop, where there is a second loop within your current for loop. This is O(n^2) due to iterating over, in the worst case, n*n elements.

Java pseudo-code for a O(n^2) run-time initializing an empty matrix:

int result[n][m];
for(int i=0; i<n; ++i){
    for(int j=0; j<m; ++j){
       result[i][j] = 0;
    }
}

Related Posts:

  1. What is C# equivalent of in C++?
  2. ‘do…while’ vs. ‘while’
  3. Visual Studio /**/ comment shortcut?
  4. C# equivalent of C++ vector, with contiguous memory?
  5. how to convert C# to C++
  6. Is dependency injection useful in C++
  7. Is dependency injection useful in C++
  8. Where to place native DLL to use Pocket PC emulator?
  9. Best way to reverse a string
  10. Critical error detected c0000374 – C++ dll returns pointer off allocated memory to C#
  11. C++ performance vs. Java/C#
  12. Best way to randomize an array with .NET
  13. Convert HTML to PDF in .NET
  14. C# HttpClient An existing connection was forcibly closed by the remote host
  15. Can anyone explain IEnumerable and IEnumerator to me? [closed]
  16. IOException: The process cannot access the file ‘file path’ because it is being used by another process
  17. Error : Index was outside the bounds of the array.
  18. No connection could be made because the target machine actively refused it?
  19. What does a lock statement do under the hood?
  20. What are the benefits to marking a field as `readonly` in C#?
  21. How to resolve “Input string was not in a correct format.” error?
  22. failed to load resource: the server response with a status 500 (internal server error)
  23. C# compiler error: “not all code paths return a value”
  24. The page was not displayed because the request entity is too large on IIS
  25. What is the purpose of nameof?
  26. Converting a String to DateTime
  27. Error 1053 the service did not respond to the start or control request in a timely fashion
  28. Only one usage of each socket address (protocol/network address/port) is normally permitted?
  29. Why should I use SerializeField?
  30. The client and server cannot communicate, because they do not possess a common algorithm – ASP.NET C# IIS TLS 1.0 / 1.1 / 1.2 – Win32Exception
  31. Cannot implicitly convert type ‘customtype’ to ‘othercustomtype’
  32. Extension methods must be defined in a non-generic static class
  33. Metadata file ‘.dll’ could not be found
  34. C# List to string with delimiter
  35. Convert a list of strings to a single string
  36. Incorrect string value: ‘\xEF\xBF\xBD’ for column
  37. How do I declare a DefaultValue attribute whose value is an array of strings?
  38. Unity3d restart current scene
  39. Easiest way to alter eBay page content/DOM
  40. Why does var evaluate to System.Object in “foreach (var row in table.Rows)”?
  41. MSHTML DLL on Windows 10
  42. Convert char to int in C#
  43. Unity 2d jumping script
  44. The remote server returned an error: (403) Forbidden
  45. ..The underlying connection was closed: An unexpected error occurred on a receive
  46. Select distinct using linq
  47. What are Virtual Methods?
  48. SQL Insert Query Using C#
  49. How to round up the result of integer division?
  50. Read and parse a Json File in C#
  51. Passing just a type as a parameter in C#
  52. The remote server returned an error: (407) Proxy Authentication Required
  53. IsNumeric function in c#
  54. The calling thread must be STA, because many UI components require this in WPF
  55. How to declare session variable in C#?
  56. Cannot open database “test” requested by the login. The login failed. Login failed for user ‘xyz\ASPNET’
  57. Writing data into CSV file in C#
  58. System.Data.SqlClient.SqlException: Login failed for user
  59. C# Print list of string array
  60. finding the maximum length of lists in c#
  61. C# Error (Cannot Implicitly convert type ‘string’ to ‘int’)
  62. “A project with an Output type of Class Library cannot be started directly”
  63. Creating a comma separated list from IList or IEnumerable
  64. EF CodeFirst: Either the parameter @objname is ambiguous or the claimed @objtype (COLUMN) is wrong
  65. Randomize a List
  66. “A project with an Output type of Class Library cannot be started directly”
  67. Conversion of a datetime2 data type to a datetime data type results out-of-range value
  68. JSON.NET Error Self referencing loop detected for type
  69. How can I cast int to enum?
  70. entity object cannot be referenced by multiple instances of IEntityChangeTracker. while adding related objects to entity in Entity Framework 4.1
  71. What does ModelState.IsValid do?
  72. When to use an Enum vs Struct
  73. How to make a simple popup box in Visual C#?
  74. windows could not start service on local computer error 5 access is denied
  75. Destroy an object in C#
  76. How can I implement static methods on an interface?
  77. How to add List<> to a List<> in asp.net [duplicate]
  78. Adding a newline into a string in C#
  79. How to format a string as a telephone number in C#
  80. How can we generate getters and setters in Visual Studio?
  81. .NET String.Format() to add commas in thousands place for a number
  82. Fastest way to generate a random boolean
  83. need implement C# Counter
  84. Invalid attempt to read when no data is present
  85. What is the simplest regular expression to validate emails to not accept them blindly?
  86. The provider did not return a ProviderManifestToken string Entity Framework
  87. Why is HttpContext.Current null?
  88. Getting selected value of a combobox
  89. How do I clone a generic list in C#?
  90. Is there a way to toggle a boolean variable in C#?
  91. Effectively use async/await with ASP.NET Web API
  92. A potentially dangerous Request.Path value was detected from the client (*)
  93. Get single listView SelectedItem
  94. .NET Core vs Mono
  95. Add item to Listview control
  96. Windows service start failure: Cannot start service from the command line or debugger [duplicate]
  97. Displaying DateTime picker instead of Date picker in ASP .NET MVC 5.1/HTML 5 specific
  98. member names cannot be the same as their enclosing type C#
  99. How to enumerate an enum
  100. How to connect to database from Unity

Leave a Comment