text: 1 vote
  2k views
  
  ### Complexity of an algorithm with multiple inputs [duplicate]
  
  I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$. But what ...
  • 111
  35k views
  
  ### How does one know which notation of time complexity analysis to use?
  
  In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
  • 1,323
  7k views
  
  ### What is the meaning of $O(m+n)$?
  
  This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
  • 1,642
  15k views
  
  ### Can a Big-Oh time complexity contain more than one variable?
  
  Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
  • 423
  2k views
  
  ### Can we test whether two vertices are connected in time linear in the number of nodes?
  
  Consider the problem: Given an undirected graph and two of its vertices, is there a path between them? I often read that this problem can be solved in linear time in the number of vertices! I am ...
  • 43
  4k views
  
  ### Time complexity based on two variables
  
  Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant $c$. ...
  • 143
  3k views
  
  • 133
  133 views
  
  ### What does it mean to add up O-terms with different variables? [duplicate]
  
  Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the answers were quite ambiguous and I couldn't find a good explanation.
  • 157
  1 vote
  126 views
  
  ### What kind of growth is $O(0.24\cdot K\cdot 2^w)$
  
  I've calculated the running time of an algorithm I'm interested in to be $$O(0.24\cdot K\cdot 2^{w})\,,$$ where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
  • 519
  82 views
  
  ### Does this program have a runtime of O(N) or O(n*m)
  
  This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure ...
  • 121
  1 vote
  84 views
  
  ### Can the following O(...) expression be simplified?
  
  I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity: $O(kn + k^2L + k^2nL + knL)$ I think I ...
  • 113
  Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
explanation: The document is a collection of questions and answers related to the complexity of algorithms, specifically focusing on Big O notation and time complexity analysis. It contains multiple questions and their corresponding answers, each addressing different aspects of algorithm complexity, such as the complexity of algorithms with multiple inputs, the meaning of $O(m+n)$, and the time complexity of determining if two vertices are connected in a graph.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: 1 vote
  2k views
  
  ### Complexity of an algorithm with multiple inputs [duplicate]
  
  I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$. But what ...
  • 111
  35k views
  
  ### How does one know which notation of time complexity analysis to use?
  
  In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
  • 1,323
  7k views
  
  ### What is the meaning of $O(m+n)$?
  
  This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
  • 1,642
  15k views
  
  ### Can a Big-Oh time complexity contain more than one variable?
  
  Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
  • 423
  2k views
  
  ### Can we test whether two vertices are connected in time linear in the number of nodes?
  
  Consider the problem: Given an undirected graph and two of its vertices, is there a path between them? I often read that this problem can be solved in linear time in the number of vertices! I am ...
  • 43
  4k views
  
  ### Time complexity based on two variables
  
  Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant $c$. ...
  • 143
  3k views
  
  • 133
  133 views
  
  ### What does it mean to add up O-terms with different variables? [duplicate]
  
  Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the answers were quite ambiguous and I couldn't find a good explanation.
  • 157
  1 vote
  126 views
  
  ### What kind of growth is $O(0.24\cdot K\cdot 2^w)$
  
  I've calculated the running time of an algorithm I'm interested in to be $$O(0.24\cdot K\cdot 2^{w})\,,$$ where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
  • 519
  82 views
  
  ### Does this program have a runtime of O(N) or O(n*m)
  
  This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure ...
  • 121
  1 vote
  84 views
  
  ### Can the following O(...) expression be simplified?
  
  I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity: $O(kn + k^2L + k^2nL + knL)$ I think I ...
  • 113
  Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document is a collection of questions and answers related to the complexity of algorithms, specifically focusing on Big O notation and time complexity analysis. It contains multiple questions and their corresponding answers, each addressing different aspects of algorithm complexity, such as the complexity of algorithms with multiple inputs, the meaning of $O(m+n)$, and the time complexity of determining if two vertices are connected in a graph.
  
  Label: multiple-question-and-answer