# 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.

278 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 11
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 ...
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 ...
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. ...
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 ...
36 views

• 73
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 ...
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 ...
1 vote
201 views