I don't understand my prof's notes relating to time complexity

[r0bHadz]

Problem Statement: I've attached a picture of his notes. For a sorted array, to update it he put: O(logn)+O(1)
Relevant Equations: O(n) + O(logn) = O(n)

I don't see how it can be O(logn)+O(1) and not O(logn)+O(n) in the worst case

After you find the index that needs updating, and you actually change the value (which is O(1),) since it is a sorted array, let's assume that the last element of that has a value gets updated and now it's updated value belongs to the very front of the array. We would have to then move (n-1) elements and make one assignment. How is that not O(n)?

[Moderator's note: Moved from a homework forum.]

 

[fresh_42]

Abstract Data Type: ADT
- Graph for relations (facebook, roadnetwork)

Organization of a Graph:
 - Adjacency List
 - Adjacency Matrix

Required Operations:
 - CRUD: Create (Insert), Retrieve (Find), Update, Delete

Implementation:

Note:
A - Array
LL - Linked List
O(logN) + O(N) --> O(N)
O(logN) + Lazy O(1) --> O(logN)
O(N) or Lazy O(1) --> O(N)

              Insert     Find
              Create   Retrieve   Update             Delete
Sorted A       O(N)      O(logN)  O(logN) + O(1)   O(logN) + (O(N) or Lazy O(1))
UnSorted A     O(1)      O(N)*    O(N) + O(1)      O(N) + (O(N) or Lazy O(1))
Sorted LL      O(N)      O(N)     O(N) + O(1)      O(N) + O(1) for link movement
Unsorted LL    O(1)      O(N)     O(N) + O(1)      O(N) + O(1)   
    

* you cannot perform binary search

Notes:
Capacity of the array: The number of elements the array can hold (english size)
Size of the array: The number of elements the array is holding

Question:
1. Why don't we do lazy deletion in a LL

 

[jbriggs444]

After you find the index that needs updating, and you actually change the value (which is O(1),) since it is a sorted array, let's assume that the last element of that has a value gets updated and now it's updated value belongs to the very front of the array. We would have to then move (n-1) elements and make one assignment. How is that not O(n)?

I suspect that the "update" in question involves a modification of data in the accessed record rather than its key.

An update that affects the key could be modeled as a delete of the old record followed by an insert of the replacement record.

 

[r0bHadz]

I suspect that the "update" in question involves a modification of data in the accessed record rather than its key.

An update that affects the key could be modeled as a delete of the old record followed by an insert of the replacement record.

and your suspicion was correct! I appreciate the reply :)

 

[jbriggs444]

and your suspicion was correct! I appreciate the reply :)

And thank you for closing the loop. Always appreciated.

 

[Jarvis323]

Not sure what your professor expects, but the correct way to view O(f(n)) is that it is a set. g(n) is in the set O(f(n)) if there is some n0, such that for all m > n0, g(n) <= cf(n), for some c.

Considering numeric addition isn't even defined for sets, what you are writing doesn't even parse logically unless you take + to be the union. Considering that O(1) is a subset of O(n), the union of O(n) and O(1) is just O(n). Likewise, the union of O(logn) and O(n) is just O(n). In other words, the union of O(n) and O(logn) means every function that is either in O(n) or in O(logn). But O(n) contains all of the functions in O(logn).

I think people tend to use + and = with Big-O notation when trying to teach the concept to people who don't know the basics of sets. You can take + to be the union, and = to mean the left side is an element of the set expressed on the right side when following people using these notations.

Breaking an algorithm into the parts and saying one part is O(f(n)) and the other is O(g(n)) makes sense, but when considering the two parts together you take the union of the two, and end up with just the set that is defined by the function with the larger or equal growth. To see why, work out the fact that O(f(n) + g(n) ) defines the same set as O(f(n)) union O(g(n)).

 

[fresh_42]

Not sure what your professor expects, but the correct way to view O(f(n)) is that it is a set. g(n) is in the set O(f(n)) if there is some n0, such that for all m > n0, g(n) <= cf(n), for some c.

That's not the way it's done in computer science. We simply count here and therefore we can write e.g.
$O(\log n)+O(n) =O(n)$ or $O(n)+O(n)=O(n)$. It makes sense, as we counted $c_0\cdot n \leq c_1\cdot \log n + c_2 \cdot n \leq (c_1 +c_2)\cdot n = O(n)$.

Sets are completely irrelevant.

 

[Jarvis323]

At least in the computer science theory courses I’ve taken, sets have been used. Maybe it’s mostly just the professor who taught it.

Without sets, I think it can be confusing, because f(n) is not equal to O(f(n)) it’s = O(f(n)) with = meaning it has this property. Sort of like saying 3 = is an integer. It’s just a convenient abuse of notation for saying 3 has the property that it is an integer, or equivalently, is an element of the set of integers. Then even O(g) = O(f) uses = in a different way than that. And the use of + is also redefined.

If you think about, you are just defining sets anyways.

So for me, using sets seems like a more clean and unambiguous way to think about it. So when I try to help people who are confused about it, I assume that thinking about it in this way will clear up any misunderstanding. You don’t need to redefine any notation.

But in the end it doesn’t matter so long as you understand it and are comfortable with the notation.