Questions tagged [big-o-notation]

Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.

Filter by
Sorted by
Tagged with
1 vote
0 answers
24 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
user avatar
0 votes
4 answers
56 views

Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?

So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
user avatar
0 votes
5 answers
115 views

Prove big O notation for $\log(n!)$ without applying Stirling's formula

I want to prove that, $$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$ The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow. Can ...
user avatar
0 votes
2 answers
91 views

Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?

I'm following an online course about Complexity and I'm learning a lot of stuff. I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here. ...
user avatar
-1 votes
0 answers
45 views

Is space complexity fixed (O(1)) in my case?

I write an algoritm in C++ that uses std::unrodered_map. I have std::unrodered_map<char, int> data structure. There are ...
user avatar
-1 votes
1 answer
36 views

Complexity of T(n)=2T(n-1)

I built a recursion tree like this: 0 / \ 0 0 /\ /\ ... ... So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum_{i=0}^{n}...
user avatar
  • 1
0 votes
2 answers
47 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
user avatar
1 vote
1 answer
81 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis: Imagine that the following big-O expressions ...
user avatar
1 vote
3 answers
58 views

Difference between an exact and Big O Notation for worst case runtime

I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm. This is what I'm struggling to ...
user avatar
1 vote
1 answer
220 views

Time complexity when taking certain elements and iterating over them?

I'm trying to gain a better understanding of Big O. Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating ...
user avatar
-2 votes
2 answers
46 views

What is the BigO of a C# function when runtime is 3n - logn + 1

I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
user avatar
  • 5
3 votes
2 answers
313 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
user avatar
  • 337
1 vote
1 answer
46 views

Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as $$T(n) ...
user avatar
1 vote
1 answer
73 views

Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

Sources: https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://www.bigocheatsheet.com/ It can be seen that a Hash Table has no access/indexing complexity given the above sources. This ...
user avatar
  • 381
1 vote
1 answer
32 views

Comparing two functions rate of growth

This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question. Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
user avatar
  • 187
-2 votes
2 answers
57 views

Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$

I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^*n$ if $n$ is odd and $n!$ if even. So my thought is to say that $f(n) = O(g(n))$ and then with the definition ...
user avatar
0 votes
1 answer
55 views

Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
user avatar
2 votes
1 answer
55 views

Which approach of mine for an algorithm upper bound is correct?

Say we have this algorithm in Python. ...
user avatar
  • 133
1 vote
1 answer
38 views

Newbie needs some explanation on the following code and O-expressed time complexity

I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations. Code example #1: ...
user avatar
  • 113
0 votes
1 answer
40 views

Possible Error in TAOCP

In section 1.2.11.2 of Donald Knuth's first volume of TAOCP, he gives an exercise at the end to prove that $g(n) = \Omega (f(n)) \iff f(n) = O(g(n))$ (exercise 13). His solution is simply: "we ...
user avatar
2 votes
3 answers
124 views

Determining Big O of a for loop nested within a while loop

I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :) Im a ...
user avatar
-1 votes
2 answers
83 views

Which is larger: $n^{3/2}$ or $n^{\log n}$?

We know that $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = c.$$ Let $f(n)=n^{3/2}$ and $g(n)=n^{\log n}.$ When I am applying L'Hôpital's rule for $$\...
user avatar
  • 1
2 votes
2 answers
70 views

Does $f(n) \in O(g(n))$ imply $2^{f(n)} \in O(2^{g(n)})$?

Is the following true: $$ f(n) \in O(g(n)) \text{ then } 2 ^ {f(n)} \in O(2^{g(n)})$$
user avatar
1 vote
1 answer
35 views

Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
user avatar
  • 149
2 votes
3 answers
96 views

$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true: $$\log_{2}{\left(\frac{1}{2}n\right)} + \log_{2}{\left(\frac{1}{4}n\right)}...
user avatar
4 votes
1 answer
361 views

Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
user avatar
1 vote
1 answer
81 views

Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
user avatar
  • 45
1 vote
1 answer
27 views

How can we assume the asymptotic complexity of 1/2n^2 - 3n

I am trying to understand how asymptotic complexity of the given function is calculated based out of Introduction to algorithms by Thomas Cormen. In the book we are trying to solve inequality for $f(n)...
user avatar
1 vote
2 answers
45 views

Calculating Big O if unknown runtime of called functions

I haven't been able to track down if there is a generally accepted practice for assigning a Big O value when dealing with functions of unknown runtime. Given the following pseudocode, with two ...
user avatar
1 vote
1 answer
78 views

Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
user avatar
1 vote
3 answers
126 views

Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
user avatar
1 vote
1 answer
48 views

What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?

What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$? I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $...
user avatar
1 vote
1 answer
57 views

Whether and how to distinguish two kinds of $O(1)$ speedup

Here is a very bad algorithm that computes $4n$ for an integer input. ...
user avatar
  • 125
1 vote
2 answers
66 views

Who said first "In practice, log log N is at most (single digit number)?"

In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like In practice, $\log(\log(N))$ is at most 9. ...the idea being that even though the ...
user avatar
  • 111
0 votes
0 answers
32 views

Is a polynomial function that is O(e^x) possible? [duplicate]

Are there any polynomial functions that are $O(e^x)$? Is this possible?
user avatar
  • 11
1 vote
4 answers
87 views

Having a lot of trouble trying to reason the formal definition of Big O

My professor recently brushed over the formal definition of Big O: To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. ...
user avatar
1 vote
1 answer
51 views

What is the big-$O$ notation of a summation of logs where the arguments add to $n$?

For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ? I found this, but is not what I'm looking for.
user avatar
7 votes
3 answers
3k views

What are you allowed to move into the big O notation for it to be still correct?

Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct? For example: Is this $\log(O(n))= O(\log(n))$ correct? Or is this correct $O(n)^2=O(...
user avatar
2 votes
3 answers
75 views

Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?

The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
user avatar
0 votes
2 answers
93 views

Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
user avatar
1 vote
1 answer
201 views

Time Complexity Sigma Notation

Consider the following pseudo-code: counter = 0 for (k = 16; k > 0; k /= 2) for (j = 0; j < k; j++) counter++ I get that the time complexity is $...
user avatar
0 votes
1 answer
92 views

Why do we consider the + |V| in big-O notation in the time complexity of BFS

It is agreed upon that the time complexity of BFS is $O(|V| + |E|)$. Breath first search usually is used within a connected component. The connected component with the least $|E|$ given a fixed $|V|$ ...
user avatar
1 vote
2 answers
65 views

Disambiguating Big-O and Theta for Expressing Time Complexity

Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ? Can ...
user avatar
2 votes
1 answer
91 views

best and worst case number of key comparisons of an algorithm

Consider the following algorithm: ...
user avatar
1 vote
2 answers
82 views

Is $O(\log x) = O(1)$?

A colleague recently brought up this argument when we were talking about big-O runtime analysis and I've been unable to find why it is incorrect: Informally, the argument goes like this: "If the ...
user avatar
  • 127
-1 votes
1 answer
73 views

Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
user avatar
0 votes
1 answer
68 views

Return indices in the two sum problem

Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
user avatar
0 votes
4 answers
116 views

How can I compare two algorithms using their Big-Oh complexities?

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of ...
user avatar
0 votes
1 answer
40 views

How can we get upper bound in terms of Big Oh notation using Master theorem?

The recursion is: T(n) = 5T(n/2) + O(n) I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound ...
user avatar
1 vote
3 answers
87 views

Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?

Hello my question is that if i have two for loops inside each other like this: ...
user avatar

1
2 3 4 5 6